Overview

Given a sequence consisting of 0s and 1s, the problem asks us to count the number of runs (consecutive blocks) of 1s that have length \(K\) or more.

Analysis

The key point of this problem is correctly identifying “blocks of consecutive congested sections.”

For example, consider the case where \(N = 10\), \(K = 3\) and the states are 1 1 1 0 1 1 0 1 1 1.

Section: 1 2 3 4 5 6 7 8 9 10
State:   1 1 1 0 1 1 0 1 1 1
         -----   ---   -----
        length 3 length 2 length 3

• First block: sections 1–3 with length 3 → \(K = 3\) or more, so emergency report 1 time
• Next block: sections 5–6 with length 2 → less than \(K = 3\), so no report
• Last block: sections 8–10 with length 3 → \(K = 3\) or more, so emergency report 1 time

The total is 2 times.

A straightforward approach of “finding each block and recording its length” is sufficient. Since it can be solved by scanning the array just once, no special optimization is needed.

Algorithm

Scan the array from left to right once, managing the count of consecutive 1s with a counter count.

1. Initialize count = 0 (length of the current consecutive 1s) and result = 0 (number of emergency reports).
2. Examine each section \(i\) in order:
   • If \(S_i = 1\), increment count by 1.
   • If \(S_i = 0\), the block is interrupted there. If count before the interruption is \(K\) or more, increment result by 1. Then reset count to 0.
3. After the loop ends, the last block may extend to the end of the array, so check count >= K once more. If the condition is satisfied, increment result by 1.
4. Output result.

Why is another check needed after the loop?

The reset and evaluation of count are performed when \(S_i = 0\) is encountered. However, if the array ends with 1, no \(S_i = 0\) appears for the last block, so it is not evaluated within the loop. Therefore, an additional check after the loop is necessary.

Complexity

• Time complexity: \(O(N)\) — just a single scan of the array
• Space complexity: \(O(N)\) — for storing the input array (the scan itself uses only \(O(1)\) variables)

Implementation Notes

• Don’t forget the final check after the loop: If the array ends with 1, the last consecutive block is not processed within the loop, so the check if count >= K after the loop is essential. Forgetting this will result in WA.

• Timing of counter reset: When \(S_i = 0\) is found, perform the evaluation first, then reset. If the order is wrong, the evaluation will not be correct.

  Source Code

N, K = map(int, input().split())
S = list(map(int, input().split()))

count = 0
result = 0
for i in range(N):
    if S[i] == 1:
        count += 1
    else:
        if count >= K:
            result += 1
        count = 0
if count >= K:
    result += 1

print(result)

---

This editorial was generated by claude4.6opus-thinking.