Overview

This problem asks us to look at consecutive intervals of length \(M\) from left to right and count how many intervals have fewer than \(K\) days of 1 (sunny days).
Instead of reconstructing the interval each time, we can solve this efficiently by updating the sunny day count as we slide the window.

Analysis

The key observation is that “adjacent intervals are almost identical.”

For example, when moving from interval \([i, i+M-1]\) to \([i+1, i+M]\):

• The leading element \(S[i]\) leaves the interval
• The new trailing element \(S[i+M]\) enters the interval

These are the only changes.
In other words, if we know the sunny day count of the previous interval, we can update the sunny day count of the next interval in constant time.

---

If we naively “count \(M\) characters for each interval”:

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

So the total is \(O((N-M+1)M)\), which in the worst case becomes \(O(NM)\), and this is too slow for \(N \le 10^6\).

Instead, by counting only the first interval, and then using a sliding window update that removes one character and adds one character, we can process everything in \(O(N)\).

Algorithm

1. Let current be the count of 1s in the first interval S[0:M].
   
2. If current < K, increment the answer ans by 1.
3. Advance the right end one position at a time (i = M ... N-1):
   • The character leaving the interval is S[i-M]. If it is '1', then current -= 1
   • The character entering the interval is S[i]. If it is '1', then current += 1
   • After the update, if current < K, then ans += 1
4. Output ans.

This process checks all intervals of length \(M\) exactly once without missing any.

Complexity

• Time complexity: \(O(N)\)
  
• Space complexity: \(O(1)\) (excluding the input string)

Implementation Notes

• In Python, the initial count of the interval can be concisely computed with S[:M].count('1').

• Pay attention to index correspondence:

  • Character leaving: S[i - M]
  • Character entering: S[i]

• Since the constraints are large, using sys.stdin.readline instead of input() is safer.

  Source Code

import sys

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

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

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

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.