/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
京都大学は毎晩西から攻撃してくるゴリラから大学を守るために大学の西側に一直線の壁を築き上げることにした。 また，攻撃が激しい位置は壁だけでは防ぎきれないため，補強材を使って対処している。 補強材の数には限りがあるが，最先端の技術により，次回に攻撃してくるゴリラの数と位置を計算できるので，それに合わせて毎日補強材を移動させている。 その効率化のために，情報学科のエリートであるあなたが呼ばれた。
一直線の壁に沿って補強材を使う位置が等間隔に N 箇所あり，左から順に 1，2，...，N の番号が付いている。 前回の攻撃に対する備えで，今，各位置 i (1 \leq i \leq N) には A_i 個の補強材が使われている。 これらの補強材のうちいくつかを移動させ，各位置 i (1 \leq i \leq N) に B_i 個以上の補強材が使われている状態にしなければならない。 ただし，位置 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
出力
条件を満たすために要する合計コストの最小値を標準出力に1行で出力せよ。
部分点
以下の追加制約を満たすデータセットに正解した場合は 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 から位置 1 へ 2 個補強材を移動させる場合の合計コストが最小である。
入力例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
このケースの入力は部分点の追加制約の1つ目，2つ目の両方を満たす。
入力例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
このケースの入力は部分点の追加制約の2つ目を満たす。
入力例5
2 1 99999999999 1234567891 1
出力例5
1234567890
入力値および出力値は32bit整数型に収まらない場合がある。
Score : 200 points
Problem Statement
Kyoto University decided to build a straight wall on the west side of the university to protect against gorillas that attack the university from the west every night. Since it is difficult to protect the university at some points along the wall where gorillas attack violently, reinforcement materials are also built at those points. Although the number of the materials is limited, the state-of-the-art technology can make a prediction about the points where gorillas will attack next and the number of gorillas that will attack at each point. The materials are moved along the wall everyday according to the prediction. You, a smart student majoring in computer science, are called to find the way to move the materials more efficiently.
Theare are N points where reinforcement materials can be build along the straight wall. They are numbered 1 through N. Because of the protection against the last attack of gorillas, A_i materials are build at point i (1 \leq i \leq N). For the next attack, the materials need to be rearranged such that at least B_i materials are built at point i (1 \leq i \leq N). It costs |i - j| to move 1 material from point i to point j. Find the minimum total cost required to satisfy the condition by moving materials. You do not need to consider the attack after the next.
Constraints
- 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
- There is at least one way to satisfy the condition.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 ... A_N B_1 B_2 ... B_N
Output
Print the minimum total cost required to satisfy the condition.
Partial Scores
30 points will be awarded for passing the test set satisfying the following:
- N \leq 100
- A_1 + A_2 + ... + A_N \leq 400
Another 30 points will be awarded for passing the test set satisfying the following:
- N \leq 10^3
Another 140 points will be awarded for passing the test set without addtional constraints and you can get 200 points in total.
Sample Input 1
2 1 5 3 1
Sample Output 1
2
It costs least to move 2 materials from point 2 to point 1.
Sample Input 2
5 1 2 3 4 5 3 3 1 1 1
Sample Output 2
6
Sample Input 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
Sample Output 3
48
The input of this test case satisfies both the first and second additional constraints.
Sample Input 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
Sample Output 4
6302172
The input of this test case satisfies the second additional constraint.
Sample Input 5
2 1 99999999999 1234567891 1
Sample Output 5
1234567890
The input and output values may exceed the range of 32-bit integer.