COCI 2016/2017 - Contest 6 - Telefoni

View as PDF

Submit solution

Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 6
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Trong một căn phòng, có ~N~ cái bàn được xếp thành một hàng ngang, lần lượt từ trái sang phải. Một số bàn có điện thoại, và một số thì không. Tất cả các điện thoại đều gặp vấn đề nên điện thoại trên bàn ~i~ sẽ đổ chuông khi điện thoại trên bàn ~j~ đổ chuông, nếu bàn ~j~ cách bàn ~i~ không quá ~D~ bàn ~(|i-j| \le D)~. Bàn đầu tiên và bàn cuối cùng luôn có điện thoại. Ban đầu, điện thoại trên bàn ngoài cùng bên trái sẽ đổ chuông. Phải đặt thêm ít nhất bao nhiêu chiếc điện thoại lên các bàn khác để điện thoại trên bàn cuối cùng cũng đổ chuông?

Input

Dòng đầu tiên gồm ~2~ số nguyên dương, ~N~ ~(1 \le N \le 300\:000)~ và ~D~ ~(1 \le D \le N)~.

Dòng tiếp theo gồm ~N~ số ~0~ hoặc ~1~. Nếu số thứ ~i~ là ~1~ thì có điện thoại ở trên bàn thứ ~i~, và nếu số thứ ~i~ là ~0~ thì ngược lại.

Output

Số nguyên duy nhất là số điện thoại tối thiểu cần đặt thêm.

Sample 1

Input
4 1
1 0 1 1
Output
1

Sample 2

Input
5 2
1 0 0 0 1
Output
1

Sample 3

Input
8 2
1 1 0 0 1 0 0 1
Output
2

Subtask

  • ~5~ test đầu tiên có ~N \le 20~.
  • ~5~ test còn lại không có điều kiện gì thêm.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.