← 返回题目列表

AtCoder · awc0046_e

E. 散步和路障

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

分数: 466 分

问题陈述

高桥正在一维数轴上散步。最初,高桥处于坐标位置 0.

高桥有 N 运动计划。执行 i-th (1 \leq i \leq N) 计划添加 D_i 到他当前的坐标。 D_i 是一个非零整数;当正值时,他朝正方向移动;当负值时,他朝负方向移动。

有 M 路障放置在数轴上。的 j-th (1 \leq j \leq M) 路障位于坐标处 X_j。执行计划时,高桥会离开当前坐标 s 协调 s + D_i,如果之间至少存在一个路障 s 和 s + D_i (包括两个端点),即如果存在 X_j 满意 \min(s,\, s + D_i) \le X_j \le \max(s,\, s + D_i),然后 碰撞 发生 并且计划无法执行。

高桥按照从 1-st 到 N-th。对于每个计划,如果发生冲突,他必须跳过该计划。如果不会发生碰撞,他可以自由选择执行或跳过该计划。

考虑所有计划后,求高桥的最大可能坐标。

约束

  • 1 \leq N \leq 5 \times 10^4
  • 0 \leq M \leq 2 \times 10^5
  • -5 \times 10^4 \leq D_i \leq 5 \times 10^4
  • D_i \neq 0
  • \displaystyle \sum_{i=1}^{N} |D_i| \leq 5 \times 10^4
  • -10^9 \leq X_j \leq 10^9
  • X_1, X_2, \ldots, X_M 都是不同的
  • 所有输入值均为整数

输入

N M
D_1 D_2 \ldots D_N
X_1 X_2 \ldots X_M
  • 第一行包含计划数量 N 和路障数量 M,用空格分隔。
  • 第二行包含坐标变化 每个计划的 D_1, D_2, \ldots, D_N ,用空格分隔。
  • 第三行包含坐标 每个路障的 X_1, X_2, \ldots, X_M ,以空格分隔。然而,如果 M = 0,未给出第三行。

输出

在一行中打印最佳选择计划时高桥的最大可能最终坐标。


示例输入 1

4 2
3 -2 4 -1
2 5

示例输出 1

0

示例输入 2

5 0
-3 1 2 -1 4

示例输出 2

7

示例输入 3

10 6
2 5 -3 6 -4 7 -8 3 4 -2
-7 8 14 19 -11 25

示例输出 3

7

示例输入 4

20 15
5 4 -6 7 -3 8 -10 6 9 -5 4 -7 12 -8 3 11 -9 2 6 -4
-20 -13 -1 10 18 27 35 44 -7 5 14 22 31 40 50

示例输出 4

4

示例输入 5

1 1
50000
0

示例输出 5

0