Overview

In this problem, it actually suffices to consider only the “contiguous interval containing the starting point \(0\) that has no barricades.”
Within that interval, we perform a reachable-position DP where each movement plan is either “used or not used,” and speed this up using bitset.

Analysis

1. The only important barricades are the nearest ones to the left and right of \(0\)

First, consider the case where there is a barricade at coordinate \(0\).

Since Takahashi starts at coordinate \(0\), any movement interval necessarily includes \(0\).
Therefore, if there is a barricade at \(0\), all movement plans collide and are impossible to execute.
In this case, the answer is \(0\).

From here on, assume there is no barricade at \(0\).

• \(L\) := the rightmost barricade to the left of \(0\)
• \(R\) := the leftmost barricade to the right of \(0\)

(If they don’t exist, treat them as \(\pm\infty\).)

Then \(0\) lies within the interval \((L, R)\).
Moreover, there are no barricades inside this interval, because \(L\) and \(R\) are defined as the closest barricades to the left and right of \(0\).

Now, when moving from the current position \(s \in (L, R)\) to \(t\):

• If \(t \in (L, R)\), the entire interval \([s,t]\) lies within \((L,R)\), so there are no barricades along the way.
• If \(t \notin (L, R)\), the movement necessarily crosses \(L\) or \(R\), causing a collision.

In other words, whether a movement is possible depends solely on whether the position after moving remains within \((L,R)\).

Therefore, barricades to the left of \(L\) or to the right of \(R\) can be ignored, since we can never reach them in the first place.

---

2. The coordinate range can be narrowed further

Let \(S = \sum_{i=1}^{N} |D_i|\).

No matter which plans are chosen, the absolute value of the total distance traveled never exceeds \(S\).
Therefore, the coordinates Takahashi can reach are always within \([-S, S]\).

Hence, the coordinates we need to consider are only

\([ [L+1, R-1] \cap [-S, S] ]\)

We can store this as an integer coordinate range \([lo, hi]\).

---

3. The rest is a “use / skip” DP

Now that we know the safe integer coordinate range, we process each plan in order with the following transitions:

• Skip the plan
• Execute the plan (only if the position after moving stays within the safe range)

For example, if the currently reachable positions are \(\{-3, 0, 2\}\) and the next movement is \(+4\), then:

• Skipping gives \(\{-3,0,2\}\) as is
• Executing gives \(\{1,4,6\}\) (excluding positions out of range)

The union of these becomes the next set of reachable positions.

---

4. A naive DP is too slow

Let the range length be \(W = hi - lo + 1\). Then \(W \le 2S+1 \le 100001\).

A straightforward DP like: - dp[i][x] = whether coordinate x is reachable after considering the first i plans

requires checking all coordinates for each plan, taking \(O(NW)\) time.
In the worst case, this is around \(5 \times 10^4 \times 10^5\), which is quite heavy.

---

5. Speeding up with bitset

Representing the set of reachable coordinates as a bitset makes this fast.

• Bit \(k\) is \(1\) ⇔ coordinate \(lo + k\) is reachable

Then, executing a movement of distance \(d\) corresponds to a bitset shift:

• When \(d > 0\): left shift << d
• When \(d < 0\): right shift >> (-d)

Since skipping is also allowed:

\([ \text{new\_reach} = \text{old\_reach} \;\;|\;\; \text{shifted} ]\)

This processes each update much faster than examining the entire array one position at a time.

Algorithm

1. Read the input.
2. If \(0\) is among the barricades, the answer is \(0\).
3. Let \(L\) be the nearest barricade to the left of \(0\), and \(R\) be the nearest barricade to the right of \(0\).
4. Compute \(S=\sum |D_i|\) and determine the integer coordinate range to consider:
   • \(lo = \max(-S, L+1)\) (if there is no barricade on the left, use \(-S\))
   • \(hi = \min(S, R-1)\) (if there is no barricade on the right, use \(S\))
5. Prepare a bitset and set only coordinate \(0\) as reachable in the initial state.
6. For each \(D_i\):
   • Save the current bitset as old
   • If \(D_i > 0\), compute old << D_i
   • If \(D_i < 0\), compute old >> (-D_i)
   • Clear bits that are out of range
   • Take the OR with old (since skipping is allowed)
7. Finally, output the maximum reachable coordinate.

Complexity

Let \(S=\sum |D_i|\) and \(W=hi-lo+1\). Then \(W \le 2S+1 \le 100001\).

• Time complexity: \(O\!\left(M + N \cdot \frac{W}{w}\right)\)
  where \(w\) is the number of bits per machine word.
  This is faster than the \(O(NW)\) naive DP without bitset.
• Space complexity: \(O(W)\) bits

Implementation Notes

• If there is a barricade at \(0\), immediately output \(0\).

• To map between bitset indices and actual coordinates, we use offset = -lo.

  • Bit offset corresponds to coordinate \(0\)

• A left shift << may cause unnecessary bits to overflow into higher positions, so always trim them with a mask.

• Negative movement is represented by a right shift >>.

• During updates, saving old = reach before using it ensures that a single plan is not used more than once.

• The final answer is obtained from the highest set bit as: \([ \text{answer} = lo + (\text{highest\_bit\_index}) ]\)

  Source Code

import sys

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N, M = data[0], data[1]
    D = data[2:2 + N]
    X = data[2 + N:2 + N + M]

    if 0 in X:
        print(0)
        return

    INF = 10**18
    L = -INF
    R = INF

    for x in X:
        if x < 0:
            if x > L:
                L = x
        else:  # x > 0
            if x < R:
                R = x

    S = sum(abs(d) for d in D)

    lo = -S if L == -INF else max(-S, L + 1)
    hi = S if R == INF else min(S, R - 1)

    width = hi - lo + 1
    mask = (1 << width) - 1
    offset = -lo

    reach = 1 << offset  # position 0

    for d in D:
        old = reach
        if d > 0:
            reach = old | ((old << d) & mask)
        else:
            reach = old | (old >> (-d))

    ans = lo + (reach.bit_length() - 1)
    print(ans)

if __name__ == "__main__":
    solve()

---

This editorial was generated by gpt-5.4-high.