Overview

On a road where locations are arranged in a straight line, given that you can open up to \(M\) blocked sections using permits, find the maximum number of locations reachable from location \(1\).

Analysis

The key point of this problem is that “the road is a straight line (no branching).”

• To proceed rightward from location \(1\), you must pass through sections \((1,2)\), \((2,3)\), … in order.
• In other words, the condition for reaching location \(k\) is:
  “The number of blocked sections (\(W_i=1\)) among sections \(1\) through \(k-1\) is at most \(M\).”
  This is because you cannot proceed further without opening all those blocked sections.

What we can conclude from this: - There is no need to deliberate over where to use the permits. To expand the reachable range, the only option is to proceed from left to right, opening blocked sections as encountered. - If you were to exhaustively search all combinations of which sections to open, there would be up to \(2^{N-1}\) possibilities, which is far too slow for \(N \le 2\times 10^5\) (TLE).

Therefore, we simply count the number of blocked sections from left to right and stop as soon as it exceeds \(M\).

Example: - When \(W = [0,1,0,1,1]\), \(M=2\):
Counting blocked sections from left: \(0,1,1,2,3\). The moment we encounter the 3rd blocked section (blocked count becomes 3), we can no longer proceed.
Thus, the number of locations reachable up to that point is the answer.

Algorithm

1. Initialize cnt = 0 (number of blocked sections encountered so far) and reachable = 1 (maximum reachable location number).
2. Iterate through sections from \(i=1\) to \(N-1\) (in the array, this is W[i-1]).
   • If \(W_i = 1\), then cnt += 1.
   • If cnt > M, we can no longer proceed rightward, so exit the loop.
   • Otherwise, location \(i+1\) is reachable, so update reachable = i+1.
3. Output reachable.

(In the provided code, due to 0-indexing, the location reachable after examining section W[i] is i+2.)

Complexity

• Time complexity: \(O(N)\) (a single pass from left to right)
• Space complexity: \(O(1)\) (no significant additional memory beyond the input)

Implementation Notes

• When \(N=1\), there are no sections, so the answer is always 1.

• By breaking the moment cnt > M, we avoid unnecessary computation.

• Since the input size can be large, using fast input methods like sys.stdin.buffer.read() is recommended.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    if N == 1:
        print(1)
        return
    W = data[2:2 + (N - 1)]

    cnt = 0
    reachable = 1
    for i, w in enumerate(W):
        if w == 1:
            cnt += 1
        if cnt > M:
            break
        reachable = i + 2  # can reach point i+2

    print(reachable)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.