Heaters

题意翻译

## 题意描述： $Vova$先生的家可以看作一个$n \times 1$的矩形，寒冷的冬天来了，$Vova$先生想让他的家里变得暖和起来。现在我们给你$Vova$先生家的平面图，其中$1$表示这个地方是加热炉，0表示这个地方什么也没有。所有加热器都有一个加热半径$r$,一个位于$a_i$加热器可以加热[$a_i-r+1,a_i+r-1$]的范围。现在，$Vova$先生想让他的整个家都变得暖和，一开始所有的加热器都是关闭的，请你求出$Vova$先生最少要开几个加热器才能使整个家变得暖和 ## 输入输出格式： ### 输入格式： 第一行:两个整数$n,r(1≤n,r≤1000)$,含义如上 第二行，n个整数，表示$Vova$家的地图 ### 输出格式： 一个整数，表示$Vova$先生至少要打开几个加热器

题目描述

Vova's house is an array consisting of $ n $ elements (yeah, this is the first problem, I think, where someone lives in the array). There are heaters in some positions of the array. The $ i $ -th element of the array is $ 1 $ if there is a heater in the position $ i $ , otherwise the $ i $ -th element of the array is $ 0 $ . Each heater has a value $ r $ ( $ r $ is the same for all heaters). This value means that the heater at the position $ pos $ can warm up all the elements in range $ [pos - r + 1; pos + r - 1] $ . Vova likes to walk through his house while he thinks, and he hates cold positions of his house. Vova wants to switch some of his heaters on in such a way that each element of his house will be warmed up by at least one heater. Vova's target is to warm up the whole house (all the elements of the array), i.e. if $ n = 6 $ , $ r = 2 $ and heaters are at positions $ 2 $ and $ 5 $ , then Vova can warm up the whole house if he switches all the heaters in the house on (then the first $ 3 $ elements will be warmed up by the first heater and the last $ 3 $ elements will be warmed up by the second heater). Initially, all the heaters are off. But from the other hand, Vova didn't like to pay much for the electricity. So he wants to switch the minimum number of heaters on in such a way that each element of his house is warmed up by at least one heater. Your task is to find this number of heaters or say that it is impossible to warm up the whole house.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ r $ ( $ 1 \le n, r \le 1000 $ ) — the number of elements in the array and the value of heaters. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 1 $ ) — the Vova's house description.

输出格式

Print one integer — the minimum number of heaters needed to warm up the whole house or -1 if it is impossible to do it.

输入输出样例

输入样例 #1

6 2
0 1 1 0 0 1

输出样例 #1

3

输入样例 #2

5 3
1 0 0 0 1

输出样例 #2

2

输入样例 #3

5 10
0 0 0 0 0

输出样例 #3

-1

输入样例 #4

10 3
0 0 1 1 0 1 0 0 0 1

输出样例 #4

3

说明

In the first example the heater at the position $ 2 $ warms up elements $ [1; 3] $ , the heater at the position $ 3 $ warms up elements $ [2, 4] $ and the heater at the position $ 6 $ warms up elements $ [5; 6] $ so the answer is $ 3 $ . In the second example the heater at the position $ 1 $ warms up elements $ [1; 3] $ and the heater at the position $ 5 $ warms up elements $ [3; 5] $ so the answer is $ 2 $ . In the third example there are no heaters so the answer is -1. In the fourth example the heater at the position $ 3 $ warms up elements $ [1; 5] $ , the heater at the position $ 6 $ warms up elements $ [4; 8] $ and the heater at the position $ 10 $ warms up elements $ [8; 10] $ so the answer is $ 3 $ .

题意翻译

## 题意描述： $Vova$先生的家可以看作一个$n \times 1$的矩形，寒冷的冬天来了，$Vova$先生想让他的家里变得暖和起来。现在我们给你$Vova$先生家的平面图，其中$1$表示这个地方是加热炉，0表示这个地方什么也没有。所有加热器都有一个加热半径$r$,一个位于$a_i$加热器可以加热[$a_i-r+1,a_i+r-1$]的范围。现在，$Vova$先生想让他的整个家都变得暖和，一开始所有的加热器都是关闭的，请你求出$Vova$先生最少要开几个加热器才能使整个家变得暖和 ## 输入输出格式： ### 输入格式： 第一行:两个整数$n,r(1≤n,r≤1000)$,含义如上 第二行，n个整数，表示$Vova$家的地图 ### 输出格式： 一个整数，表示$Vova$先生至少要打开几个加热器