AT_kupc2016_h.壁壁壁壁壁壁壁

为了保护京都大学免受每天晚上从西边袭来的大猩猩的攻击，学校决定在大学西侧修建一堵直线的墙。此外，对于攻击特别激烈的位置，仅靠墙体无法防御，因此还需要使用补强材料进行加固。补强材料的数量有限，但借助最先进的技术，可以预测下次大猩猩攻击的位置和数量，因此每天都会根据预测调整补强材料的位置。为了提高效率，信息学科的精英——你，被召集来解决这个问题。

沿着这堵直线的墙，有 $N$ 个等间隔的位置可以使用补强材料，编号从左到右依次为 $1, 2, \ldots, N$。为了应对上一次的攻击，目前每个位置 $i$（$1 \leq i \leq N$）使用了 $A_i$ 个补强材料。现在需要移动其中的一些补强材料，使得每个位置 $i$（$1 \leq i \leq N$）最终至少有 $B_i$ 个补强材料。将一个补强材料从位置 $i$ 移动到位置 $j$ 的花费为 $|i - j|$。请多次进行这样的移动，使得满足条件所需的总花费最小。下次攻击之后的情况无需考虑。

输入通过标准输入给出，格式如下：

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

请输出满足条件所需的最小总花费，输出一行。

附加分说明

对于满足以下附加限制的数据集，分别可获得 $30$ 分的部分分。

• $N \leq 100$
• $A_1 + A_2 + \cdots + A_N \leq 400$

对于满足以下附加限制的数据集，可再获得 $30$ 分的部分分。

• $N \leq 10^3$

对于没有附加限制的数据集，若答对可再获得 $140$ 分，总分为 $200$ 分。

限制条件

• $1 \leq N \leq 10^5$
• $A_i \geq 1$
• $B_i \geq 1$
• $A_1 + A_2 + \cdots + A_N \leq 10^{12}$
• $B_1 + B_2 + \cdots + B_N \leq A_1 + A_2 + \cdots + A_N$
• 一定存在满足条件的移动方案

样例解释 1

将位置 $2$ 的 $2$ 个补强材料移动到位置 $1$，总花费最小。

样例解释 3

该输入满足部分分附加限制的第一个和第二个条件。

样例解释 4

该输入满足部分分附加限制的第二个条件。

样例解释 5

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

由 ChatGPT 4.1 翻译