← 返回比赛

已结束 COCR 提高赛 #1

← 上一题下一题 →

A4765 | $重复の任务$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

孜孜不倦地做任务……？ JW 的学校举办了一个线上活动，参加者需要完成 $N$ 个任务就可以获得超级大礼。JW 当然是要参加的。但是，学校为了培养学生们的思维，所有任务都非常的复杂。 JW 觉得任务很简单，不就是给同学们送祝福，然后统计送祝福数量和收到“同祝”数量吗。他直接设 $f(x)$ 表示第 $x$ 个任务的送祝福数量与收到“同祝”数量的和，最后答案就是 $\sum_{i=1}^N f(i)$。JW 有无数个男同学和女同学，第 $1$ 个任务需要给 $a_1$ 个男同学送祝福，再给 $b_1$ 个女同学送祝福，然后，会收到 $\max(a_1,b_1)$ 个“同祝”。 接下来的任务就没那么简单了。对于第 $i$ 个任务（$i \geq 2$），需要完成第 $a_i,a_i+1,a_i+2,\ldots,b_i$ 个任务，然后会收到 $\max_{0 \leq j \leq b_i-a_i}f(a_i+j)$ 个“同祝”。当然，最后这些任务都会转化成若干个任务 $1$。 但是，JW 的精力毕竟是有限的，处理每个任务也是需要花费一定的精力的。现在我们认为 JW 的精力是 $w_0$，处理好第 $i$ 个任务的精力花费是 $w_i$，但是可以获得 $f(i)$ 个“同祝”。然而，第 $i$ 对同学可能有 $k_i$ 个一模一样的任务。。JW 为了让他的 rp++，肯定是要积累最多的“同祝”数量，所以现在请你帮他算出来在他的精力用完前最多能收集到多少个的“同祝”。

输入格式

输入共 $5$ 行： 第一行有 $1$ 个正整数 $N$，含义见题目描述； 第二行有 $N$ 个正整数 $a_i$，含义见题目描述； 第三行有 $N$ 个正整数 $b_i$，含义见题目描述； 第四行有 $N+1$ 个正整数 $w_i(0 \rightarrow N)$，含义见题目描述； 第五行有 $N$ 个正整数 $k_i$，含义见题目描述。

输出格式

输出一个数，表示 JW 在精力用完前能累计多少个“同祝”。

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

输入 #3

4
2 1 1 1
4 1 2 3
19 10 3 7 2
7 2 4 2

输出 #3

【数据范围】 对于所有数据，保证： $1 \leq N \leq 5 \times 10^3$，$1 \leq a_1,b_1 \leq 10^5$，$1\leq w_i \leq500$，$1\leq k_i \leq10^3$，$1 \leq a_i \leq b_i < i$（$i \geq 2$），$w_i\le w_0$（$i\geq1$） 测试点$N\le$$k\le$特殊性质1$10$$1$无2$100$$500$无3,4,5$10^3$$500$A6$10^3$$500$B7,8,9$10^3$$500$无10$5 \times 10^3$$500$B11$5 \times 10^3$$1$无12~20$5\times 10^3$$10^3$无 特殊性质 A：保证有 $a_i=1,b_i=i-1$（$i \geq 2$）。 特殊性质 B：保证有 $a_1=b_1=1$。 本题测试点等分。 【样例解释】 样例组 #1： $$ f(1)=1+1+\max(1,1)=3 \\ f(2)=f(1)+f(1)=6 \\ f(3)=f(1)+f(2)+\max(f(1),f(2))=15 $$ JW 共有 $10$ 点精力，完成每个任务分别需要 $\{10,5,5\}$ 点精力，一种可能的最优的方式是选择完成第 $2$ 和 $3$ 个任务各 $1$ 次，可获得 $f(2)+f(3)=21$ 个“同祝”。 样例组 #2: $$ f(1)=3+4+\max(3,4)=11 \\ f(2)=f(1)+f(1)=22 \\ f(3)=f(1)+f(1)=22 \\ f(4)=f(1)+f(1)=22 $$ JW 共有 $8$ 点精力，完成每个任务分别需要 $\{2,4,1,1\}$ 点精力，一种可能的最优方式是可以完成所有任务各 $1$ 次，可获得 $1\times f(1)+1\times f(2)+1\times f(3)+1\times f(4)=77$ 个“同祝”。 样例组 #3: $$ f(1)=2+4+\max(2,4)=10 \\ f(2)=f(1)+f(1)=20 \\ f(3)=f(1)+f(2)+\max(f(1),f(2))=50 \\ f(4)=f(1)+f(2)+f(3)+\max(f(1),f(2),f(3))=130 $$ JW 共有 $19$ 点精力，完成每个任务分别需要 $\{10,3,7,2\}$ 点精力，一种可能的最优的方式是选择完成第 $3$ 个任务 $2$ 次和第 $4$ 个任务 $2$ 次，可获得 $2\times f(3)+2\times f(4)=360$ 个“同祝”。

C++ 编辑器

输入

输出