AT_abc318_f [ABC318F] Octopus

题目描述

在数轴上有 $1$ 个章鱼机器人和 $N$ 个宝藏。第 $i$ 个宝藏位于坐标 $X_i$ 上（$1 \leq i \leq N$）。 章鱼机器人有 $1$ 个头和 $N$ 条腿，第 $i$ 条腿的长度为 $L_i$（$1 \leq i \leq N$）。

请你求出满足以下条件的整数 $k$ 的个数，使得机器人能够抓取全部 $N$ 件宝物：

• 将头放在坐标 $k$ 上。
• 按照 $i=1,2,\ldots,N$ 的顺序，重复以下操作：“在距离头部 $L_i$ 以内的范围内，即满足 $k-L_i \leq x \leq k+L_i$ 的坐标 $x$ 上，如果还有未被抓取的宝藏，则从中选择一个宝藏并抓取。”

输入格式

输入以以下格式从标准输入读入。

$N$ $X_1$ $X_2$ $\ldots$ $X_N$ $L_1$ $L_2$ $\ldots$ $L_N$

输出格式

输出满足题目条件的整数 $k$ 的个数。

输入输出样例 #1

输入 #1

3
-6 0 7
3 5 10

输出 #1

6

输入输出样例 #2

输入 #2

1
0
1000000000000000000

输出 #2

2000000000000000001

输入输出样例 #3

输入 #3

2
-100 100
1 1

输出 #3

0

说明/提示

限制条件

• $1 \leq N \leq 200$
• $-10^{18} \leq X_1 < X_2 < \cdots < X_N \leq 10^{18}$
• $1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq 10^{18}$
• 输入均为整数

样例解释 1

$k=-3,-2,-1,2,3,4$ 满足条件。例如，当 $k=-3$ 时，可以如下抓取全部 $3$ 个宝藏：

• 第 $1$ 条腿可以抓取 $-6 \leq x \leq 0$ 范围内的宝藏。其中抓取坐标 $-6$ 的第 $1$ 个宝藏。
• 第 $2$ 条腿可以抓取 $-8 \leq x \leq 2$ 范围内的宝藏。其中抓取坐标 $0$ 的第 $2$ 个宝藏。
• 第 $3$ 条腿可以抓取 $-13 \leq x \leq 7$ 范围内的宝藏。其中抓取坐标 $7$ 的第 $3$ 个宝藏。

样例解释 2

所有 $-10^{18}$ 以上 $10^{18}$ 以下的整数都满足条件。

样例解释 3

不存在满足条件的 $k$。

由 ChatGPT 4.1 翻译