Overview

This problem requires examining all contiguous intervals of length \(M\) and counting the number of intervals where the count of 1s is less than \(K\).
Instead of recounting the number of 1s from scratch for each interval, we use a sliding window to efficiently update the count.

Analysis

In this problem, the intervals are:

• Day \(1\) to Day \(M\)
• Day \(2\) to Day \(M+1\)
• Day \(3\) to Day \(M+2\)
• …

shifting one day to the right at a time.

Naive Approach

If we consider counting the number of 1s in the substring of length \(M\) for each interval:

• The number of intervals is \(N - M + 1\)
• Counting each interval takes \(O(M)\)

So the total is \(O((N-M+1) \times M)\), which in the worst case becomes \(O(NM)\).

Given the constraint \(N \leq 10^6\), if \(M\) is similarly large, this is far too slow.

Key Observation

Adjacent intervals share almost all the same elements.

For example, comparing the intervals:

• \([i-M+1, i]\)
• \([i-M+2, i+1]\)

The only difference is:

• One character leaves from the left end
• One character is added to the right end

In other words, if we know the count of 1s in the previous interval:

• If the leaving character is 1, subtract \(1\)
• If the entering character is 1, add \(1\)

This gives us the count of 1s in the next interval.

This allows us to process each interval in \(O(1)\), making the overall complexity \(O(N)\).

Concrete Example

For example, let:

• \(S =\) 10110
• \(M = 3\)
• \(K = 2\)

The count of 1s in the first interval 101 is \(2\).
The next interval is 011, which differs from the previous interval by:

• The leftmost 1 leaves → \(-1\)
• The rightmost 1 enters → \(+1\)

So we can immediately tell the count remains \(2\).

By updating this way instead of recounting each time, the algorithm runs efficiently.

Algorithm

1. Count the number of 1s in the first interval of length \(M\), S[:M].
2. If that count is less than \(K\), add \(1\) to the answer.
3. Then, slide the interval one character to the right at a time, performing the following:
   • If the character leaving the interval S[i-M] is 1, decrease the count by \(1\)
   • If the character entering the interval S[i] is 1, increase the count by \(1\)
   • If the updated count is less than \(K\), add \(1\) to the answer
4. Output the final answer.

This method is known as the sliding window technique.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• The count of 1s in the first interval is computed using S[:M].count('1').

• After that, instead of recounting each time, we update by only looking at the leaving character and the entering character.

• In the loop for i in range(M, N):, S[i] is the newly entering character, and S[i-M] is the leaving character.

• Since the input size can be large, sys.stdin.readline is used for fast input.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    S = input().strip()

    cnt = S[:M].count('1')
    ans = 1 if cnt < K else 0

    for i in range(M, N):
        if S[i - M] == '1':
            cnt -= 1
        if S[i] == '1':
            cnt += 1
        if cnt < K:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.