/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は N 個の電球が一列に並んだ装飾パネルを持っています。それぞれの電球には左から順に 1 から N までの番号が付けられており、各電球は「点灯」か「消灯」のどちらかの状態になっています。
各電球の初期状態は整数 A_i で与えられます。A_i = 0 のとき電球 i は点灯しており、A_i = 1 のとき電球 i は消灯しています。
高橋君は以下の操作を好きな回数（ 0 回でも可）行うことができます。
- 整数 i（1 \leq i \leq N - K + 1）を 1 つ選び、電球 i, i+1, \ldots, i+K-1 の状態をすべて反転させる。すなわち、この連続する K 個の電球のうち、点灯していたものは消灯し、消灯していたものは点灯する。
各操作で選ぶ i の値は毎回自由に決めることができ、以前と同じ値を再び選ぶこともできます。
高橋君は、すべての電球を点灯状態（すなわち、すべての i に対して A_i = 0 の状態）にしたいと考えています。これが可能かどうかを判定し、可能な場合は必要な最小操作回数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- A_i \in \{0, 1\} (1 \leq i \leq N)
- 入力はすべて整数である
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、電球の個数を表す整数 N と、1 回の操作で反転させる電球の個数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各電球の初期状態を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- A_i = 0 のとき、電球 i は点灯している。
- A_i = 1 のとき、電球 i は消灯している。
出力
すべての電球を点灯状態にすることが可能な場合は、必要な最小操作回数を 1 行で出力してください。
不可能な場合は、-1 を 1 行で出力してください。
入力例 1
5 3 0 1 1 1 0
出力例 1
1
入力例 2
4 2 1 0 0 1
出力例 2
3
入力例 3
10 3 1 1 1 0 0 0 1 1 1 0
出力例 3
2
Score : 400 pts
Problem Statement
Takahashi has a decorative panel with N light bulbs arranged in a row. The bulbs are numbered from 1 to N from left to right, and each bulb is in one of two states: "on" or "off".
The initial state of each bulb is given by an integer A_i. When A_i = 0, bulb i is on, and when A_i = 1, bulb i is off.
Takahashi can perform the following operation any number of times (possibly zero):
- Choose an integer i (1 \leq i \leq N - K + 1) and toggle the states of bulbs i, i+1, \ldots, i+K-1. That is, among these K consecutive bulbs, those that are on are turned off, and those that are off are turned on.
The value of i chosen in each operation can be decided freely each time, and it is allowed to choose the same value as before.
Takahashi wants to turn all bulbs on (that is, reach the state where A_i = 0 for all i). Determine whether this is possible, and if so, find the minimum number of operations required.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- A_i \in \{0, 1\} (1 \leq i \leq N)
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of bulbs and an integer K representing the number of bulbs toggled in one operation, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the initial state of each bulb, separated by spaces.
- When A_i = 0, bulb i is on.
- When A_i = 1, bulb i is off.
Output
If it is possible to turn all bulbs on, output the minimum number of operations required in one line.
If it is impossible, output -1 in one line.
Sample Input 1
5 3 0 1 1 1 0
Sample Output 1
1
Sample Input 2
4 2 1 0 0 1
Sample Output 2
3
Sample Input 3
10 3 1 1 1 0 0 0 1 1 1 0
Sample Output 3
2