Kyoto University Programming Contest 2016

H - 壁壁壁壁壁壁壁 / WAAAAAAAAAAAAALL


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 200

問題文

京都大学は毎晩西から攻撃してくるゴリラから大学を守るために大学の西側に一直線の壁を築き上げることにした。 また,攻撃が激しい位置は壁だけでは防ぎきれないため,補強材を使って対処している。 補強材の数には限りがあるが,最先端の技術により,次回に攻撃してくるゴリラの数と位置を計算できるので,それに合わせて毎日補強材を移動させている。 その効率化のために,情報学科のエリートであるあなたが呼ばれた。

一直線の壁に沿って補強材を使う位置が等間隔に N 箇所あり,左から順に 12,...,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 から位置 12 個補強材を移動させる場合の合計コストが最小である。

入力例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.


Source name

KUPC2016

Submit提出する