/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の数列 A = (A_1, A_2, A_3, \dots, A_N), B = (B_1, B_2, B_3, \dots, B_N) が与えられます。
以下の操作を繰り返す (1 回も行わなくてもよい) ことで A を B に一致させることが可能かを判定してください。また、可能なら、A を B に一致させるのに必要な最小の操作回数を求めてください。
- 1 \le i \lt N を満たす整数 i を選び、以下のことを順に行う
- A_i と A_{i + 1} を入れ替える
- A_i に 1 を足す
- A_{i + 1} から 1 を引く
制約
- 2 \le N \le 2 \times 10^5
- 0 \le A_i \le 10^9
- 0 \le B_i \le 10^9
- 入力に含まれる値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 A_3 \dots A_N B_1 B_2 B_3 \dots B_N
出力
A を B に一致させることが不可能なら -1 を出力せよ。
可能なら、そのために必要な最小の操作回数を出力せよ。
入力例 1
3 3 1 4 6 2 0
出力例 1
2
以下のように操作すると、2 回の操作で A を B に一致させることができます。
- まず、i = 2 として操作する。A = (3, 5, 0) となる。
- 次に、i = 1 として操作する。A = (6, 2, 0) となる。
1 回以下の操作で目的を達成することはできません。
入力例 2
3 1 1 1 1 1 2
出力例 2
-1
この場合、A を B に一致させることは不可能です。
入力例 3
5 5 4 1 3 2 5 4 1 3 2
出力例 3
0
1 回も操作をしなくても A が B に一致している可能性があります。
入力例 4
6 8 5 4 7 4 5 10 5 6 7 4 1
出力例 4
7
Score : 500 points
Problem Statement
Given are two sequences of length N each: A = (A_1, A_2, A_3, \dots, A_N) and B = (B_1, B_2, B_3, \dots, B_N).
Determine whether it is possible to make A equal B by repeatedly doing the operation below (possibly zero times). If it is possible, find the minimum number of operations required to do so.
- Choose an integer i such that 1 \le i \lt N, and do the following in order:
- swap A_i and A_{i + 1};
- add 1 to A_i;
- subtract 1 from A_{i + 1}.
Constraints
- 2 \le N \le 2 \times 10^5
- 0 \le A_i \le 10^9
- 0 \le B_i \le 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 A_3 \dots A_N B_1 B_2 B_3 \dots B_N
Output
If it is impossible to make A equal B, print -1.
Otherwise, print the minimum number of operations required to do so.
Sample Input 1
3 3 1 4 6 2 0
Sample Output 1
2
We can match A with B in two operations, as follows:
- First, do the operation with i = 2, making A = (3, 5, 0).
- Next, do the operation with i = 1, making A = (6, 2, 0).
We cannot meet our objective in one or fewer operations.
Sample Input 2
3 1 1 1 1 1 2
Sample Output 2
-1
In this case, it is impossible to match A with B.
Sample Input 3
5 5 4 1 3 2 5 4 1 3 2
Sample Output 3
0
A may equal B before doing any operation.
Sample Input 4
6 8 5 4 7 4 5 10 5 6 7 4 1
Sample Output 4
7