← 返回题目列表

AtCoder · kupc2016_h

H. 哇啊啊啊啊啊啊

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

京都大学决定在大学西侧修建一堵直墙,以防御每晚从西面袭击大学的大猩猩。 由于墙体上一些大猩猩猛烈攻击的地方很难保护大学,因此也在这些地方建造了加固材料。 尽管材料数量有限,但最先进的技术可以预测大猩猩接下来会攻击的点以及每个点攻击的大猩猩数量。 材料每天根据预测沿着墙壁移动。 你,一个聪明的计算机科学专业学生,被要求找到更有效地移动材料的方法。

有 N 指出可以沿着直墙建造加固材料。他们有编号 1 通过 N。 因为抵御了大猩猩的最后一次攻击, A_i 材料在点构建 i (1 \leq i \leq N)。 对于下一次攻击,需要重新排列材料,使得至少 B_i 材料在点构建 i (1 \leq i \leq N)。 它的成本 |i - j| 移动 1 材料自点 i 点 j。 求通过移动物料满足条件所需的最小总成本。 您无需考虑下一次之后的攻击。

约束

  • 1 \leq N \leq 10^5
  • A_i \geq 1
  • B_i \geq 1
  • A_1 + A_2 + ... + A_N \leq 10^{12}
  • B_1 + B_2 + ... + B_N \leq A_1 + A_2 + ... + A_N
  • 至少有一种方法可以满足该条件。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

输出

打印满足条件所需的最低总成本。

部分分数 通过满足以下条件的测试集将获得

30 积分:

  • N \leq 100
  • A_1 + A_2 + ... + A_N \leq 400

另一个 30 积分:

  • N \leq 10^3

另一个 140 分数将在没有额外限制的情况下通过测试集而获得,您可以获得 总共 200 分。


样本输入 1

2
1 5
3 1

示例输出 1

2

移动成本最低 2 材料自点 2 点 1.

示例输入 2

5
1 2 3 4 5
3 3 1 1 1

示例输出 2

6

示例输入 3

27
46 3 4 2 10 2 5 2 6 7 20 13 9 49 3 8 4 3 19 9 3 5 4 13 9 5 7
10 2 5 6 2 6 3 2 2 5 3 11 13 2 2 7 7 3 9 5 13 4 17 2 2 2 4

示例输出 3

48

该测试用例的输入满足第一和第二附加约束。

示例输入 4

18
3878348 423911 8031742 1035156 24256 10344593 19379 3867285 4481365 1475384 1959412 1383457 164869 4633165 6674637 9732852 10459147 2810788
1236501 770807 4003004 131688 1965412 266841 3980782 565060 816313 192940 541896 250801 217586 3806049 1220252 1161079 31168 2008961

示例输出 4

6302172

该测试用例的输入满足第二个附加约束。

示例输入 5

2
1 99999999999
1234567891 1

示例输出 5

1234567890

输入和输出值可能超出 32 位整数的范围。