← 返回题目列表

AtCoder · arc120_c

C. 互换 2

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

分数: 500 点

问题陈述

给出两个长度序列 N 每个: A = (A_1, A_2, A_3, \dots, A_N) 和 B = (B_1, B_2, B_3, \dots, B_N).
判断是否可以使 A 等于 B 通过重复执行以下操作(可能零次)。如果可能的话,找出执行此操作所需的最少操作数。

  • 选择一个整数 i 这样 1 \le i \lt N,并按顺序执行以下操作:
    • 交换 A_i 和 A_{i + 1};
    • 添加 1 to A_i;
    • 减去 1 来自 A_{i + 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

我们可以匹配 A 与 B 分两次操作,如下:

  • 首先,执行操作 i = 2,制作 A = (3, 5, 0).
  • 接下来,执行操作 i = 1,制作 A = (6, 2, 0).

我们无法通过一次或更少的操作来实现我们的目标。


示例输入 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

A 可能等于 B 在进行任何操作之前。


示例输入 4

6
8 5 4 7 4 5
10 5 6 7 4 1

示例输出 4

7