C - Checking Weather on Consecutive Days Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は N 日間の天気を記録しました。

各日の天気は、長さ N の文字列 S で表されます。S の i 文字目が 1 なら i 日目は晴れ、0 なら i 日目は晴れでなかったことを意味します。

高橋君は、1 日ずつずらしながら連続する M 日間の天気を振り返ります。具体的には、i 日目から i + M - 1 日目までの M 日間 (1 \leq i \leq N - M + 1) を 1 つの区間とします。ある区間の中で晴れの日数が K 日未満であるとき、その区間を「悪天候期間」と呼びます。

N - M + 1 個の区間のうち、「悪天候期間」であるものの個数を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq N
  • 0 \leq K \leq M
  • N, M, K は整数
  • S は 0 と 1 のみからなる長さ N の文字列である

入力

N M K
S

1 行目に、日数 N、連続して確認する日数 M、晴れの日数の基準 K がスペース区切りで与えられる。

2 行目に、各日の天気を表す長さ N の文字列 S が与えられる。

出力

「悪天候期間」である区間の個数を 1 行で出力せよ。

入力例 1

5 3 2
10101

出力例 1

1

入力例 2

4 2 1
0000

出力例 2

3

入力例 3

12 5 3
110010111000

出力例 3

3

入力例 4

24 7 4
101101001110100110101011

出力例 4

3

入力例 5

1 1 0
0

出力例 5

0

Score : 300 pts

Problem Statement

Takahashi recorded the weather over N days.

The weather for each day is represented by a string S of length N. If the i-th character of S is 1, it means day i was sunny; if it is 0, it means day i was not sunny.

Takahashi reviews the weather over consecutive M-day periods, shifting by one day at a time. Specifically, the M days from day i to day i + M - 1 (1 \leq i \leq N - M + 1) form one interval. If the number of sunny days within an interval is less than K, that interval is called a "bad weather period."

Find the number of "bad weather periods" among the N - M + 1 intervals.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq N
  • 0 \leq K \leq M
  • N, M, K are integers
  • S is a string of length N consisting only of 0 and 1

Input

N M K
S

The first line contains the number of days N, the number of consecutive days to check M, and the sunny day threshold K, separated by spaces.

The second line contains a string S of length N representing the weather for each day.

Output

Output the number of intervals that are "bad weather periods" in a single line.

Sample Input 1

5 3 2
10101

Sample Output 1

1

Sample Input 2

4 2 1
0000

Sample Output 2

3

Sample Input 3

12 5 3
110010111000

Sample Output 3

3

Sample Input 4

24 7 4
101101001110100110101011

Sample Output 4

3

Sample Input 5

1 1 0
0

Sample Output 5

0