/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
高橋君は、1 次元の数直線上を散歩しています。高橋君は最初、座標 0 にいます。
高橋君は N 個の移動プランを持っています。i 番目 (1 \leq i \leq N) のプランを実行すると、現在の座標に D_i が加算されます。D_i は 0 でない整数で、正のとき正の方向へ、負のとき負の方向へ移動します。
数直線上には M 個のバリケードが設置されており、j 番目 (1 \leq j \leq M) のバリケードは座標 X_j にあります。あるプランの実行により現在の座標 s から座標 s + D_i へ移動するとき、s と s + D_i の間（両端を含む）にバリケードが 1 つでも存在する場合、すなわち \min(s,\, s + D_i) \le X_j \le \max(s,\, s + D_i) を満たす X_j が存在する場合、そのプランは衝突が起こるため実行できません。
高橋君はプランを 1 番目から N 番目まで順番に検討します。各プランについて、衝突が起こる場合はそのプランをスキップしなければなりません。衝突が起こらない場合は、そのプランを実行するかスキップするかを自由に選べます。
すべてのプランの検討が終わった後の、高橋君の座標としてありえる最大値を求めてください。
制約
- 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
- 1 行目には、プランの個数 N とバリケードの個数 M がスペース区切りで与えられる。
- 2 行目には、各プランによる座標の変化量 D_1, D_2, \ldots, D_N がスペース区切りで与えられる。
- 3 行目には、各バリケードの座標 X_1, X_2, \ldots, X_M がスペース区切りで与えられる。ただし、M = 0 の場合、3 行目は与えられない。
出力
最適にプランを選択したときの、最終的な高橋君の座標の最大値を 1 行で出力せよ。
入力例 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
Score : 466 pts
Problem Statement
Takahashi is taking a walk on a one-dimensional number line. Initially, Takahashi is at coordinate 0.
Takahashi has N movement plans. Executing the i-th (1 \leq i \leq N) plan adds D_i to his current coordinate. D_i is a non-zero integer; when positive, he moves in the positive direction, and when negative, he moves in the negative direction.
There are M barricades placed on the number line. The j-th (1 \leq j \leq M) barricade is at coordinate X_j. When executing a plan moves Takahashi from his current coordinate s to coordinate s + D_i, if there exists at least one barricade between s and s + D_i (inclusive of both endpoints), that is, if there exists an X_j satisfying \min(s,\, s + D_i) \le X_j \le \max(s,\, s + D_i), then a collision occurs and the plan cannot be executed.
Takahashi considers the plans in order from the 1-st to the N-th. For each plan, if a collision would occur, he must skip that plan. If no collision would occur, he may freely choose to either execute or skip the plan.
Find the maximum possible coordinate of Takahashi after all plans have been considered.
Constraints
- 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 are all distinct
- All input values are integers
Input
N M D_1 D_2 \ldots D_N X_1 X_2 \ldots X_M
- The first line contains the number of plans N and the number of barricades M, separated by a space.
- The second line contains the coordinate changes D_1, D_2, \ldots, D_N for each plan, separated by spaces.
- The third line contains the coordinates X_1, X_2, \ldots, X_M of each barricade, separated by spaces. However, if M = 0, the third line is not given.
Output
Print in one line the maximum possible final coordinate of Takahashi when plans are chosen optimally.
Sample Input 1
4 2 3 -2 4 -1 2 5
Sample Output 1
0
Sample Input 2
5 0 -3 1 2 -1 4
Sample Output 2
7
Sample Input 3
10 6 2 5 -3 6 -4 7 -8 3 4 -2 -7 8 14 19 -11 25
Sample Output 3
7
Sample Input 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
Sample Output 4
4
Sample Input 5
1 1 50000 0
Sample Output 5
0