/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は、ある高速道路の交通管制センターで渋滞監視の仕事をしています。
高速道路には N 個の区間が一列に並んでおり、起点側から順に区間 1 , 区間 2 , \ldots , 区間 N と番号が付けられています。各区間には渋滞しているかどうかの情報があり、区間 i の状態は S_i で表されます（ S_i = 1 なら渋滞中、 S_i = 0 なら通常）。
高橋君はモニターで全区間の渋滞状況を確認し、渋滞中の区間が連続している箇所に着目して報告を行います。
ここで、渋滞ブロックを次のように定義します：
渋滞中の区間の極大な連続部分を渋滞ブロックと呼びます。すなわち、区間 l, l+1, \ldots, r （1 \leq l \leq r \leq N）が以下の条件をすべて満たすとき、区間 l から区間 r までのひとまとまりを長さ r - l + 1 の渋滞ブロックと呼びます：
- S_l = S_{l+1} = \cdots = S_r = 1 である。
- l = 1 または S_{l-1} = 0 である。
- r = N または S_{r+1} = 0 である。
高橋君は、各渋滞ブロックについて以下の判断を行います：
- その渋滞ブロックの長さが K 以上であれば、大規模渋滞と判断し、上司への緊急報告を 1 回行う。
- その渋滞ブロックの長さが K 未満であれば、通常の対応で処理する（緊急報告は発生しない）。
すべての渋滞ブロックに対してこの判断を行ったとき、緊急報告が合計何回発生するかを求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- S_i \in \{0, 1\} （1 \leq i \leq N）
- 入力はすべて整数である。
入力
N K S_1 S_2 \ldots S_N
1 行目には、区間の数 N と、緊急報告の対象となる渋滞ブロックの長さの閾値 K が、スペース区切りで与えられる。
2 行目には、各区間の状態 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。 S_i = 1 は区間 i が渋滞中であること、 S_i = 0 は通常であることを意味する。
出力
緊急報告が発生する合計回数を 1 行で出力せよ。
入力例 1
10 3 0 1 1 1 0 1 1 0 1 1
出力例 1
1
入力例 2
15 2 1 1 0 1 0 1 1 1 1 0 0 1 1 0 1
出力例 2
3
入力例 3
20 4 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1
出力例 3
2
Score : 300 pts
Problem Statement
Takahashi works at the traffic control center of a highway, monitoring traffic congestion.
The highway consists of N sections arranged in a line, numbered section 1, section 2, \ldots, section N in order from the starting point. Each section has information about whether it is congested or not, and the state of section i is represented by S_i (S_i = 1 means congested, S_i = 0 means normal).
Takahashi checks the congestion status of all sections on a monitor and makes reports focusing on places where congested sections are consecutive.
Here, we define a congestion block as follows:
A maximal contiguous subsequence of congested sections is called a congestion block. That is, when sections l, l+1, \ldots, r (1 \leq l \leq r \leq N) satisfy all of the following conditions, the group of sections from section l to section r is called a congestion block of length r - l + 1:
- S_l = S_{l+1} = \cdots = S_r = 1.
- l = 1 or S_{l-1} = 0.
- r = N or S_{r+1} = 0.
For each congestion block, Takahashi makes the following judgment:
- If the length of the congestion block is K or more, it is judged as a large-scale congestion, and an emergency report is made once to his supervisor.
- If the length of the congestion block is less than K, it is handled with normal procedures (no emergency report is generated).
After making this judgment for all congestion blocks, determine the total number of emergency reports generated.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- S_i \in \{0, 1\} (1 \leq i \leq N)
- All input values are integers.
Input
N K S_1 S_2 \ldots S_N
The first line contains the number of sections N and the threshold length K for congestion blocks that require an emergency report, separated by a space.
The second line contains the states of each section S_1, S_2, \ldots, S_N, separated by spaces. S_i = 1 means section i is congested, and S_i = 0 means it is normal.
Output
Output the total number of emergency reports generated in a single line.
Sample Input 1
10 3 0 1 1 1 0 1 1 0 1 1
Sample Output 1
1
Sample Input 2
15 2 1 1 0 1 0 1 1 1 1 0 0 1 1 0 1
Sample Output 2
3
Sample Input 3
20 4 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1
Sample Output 3
2