printРабочее место участника

printЗадачи

2351. Передача сообщений

Ограничения: время – 500ms/1000ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В аудитории стоит ряд из `N` столов. За некоторыми из них сидят студенты. Петя сидит за первым столом, Маша – за `N`-м. Петя хочет незаметно от преподавателя передавать и получать сообщения от Маши. Для незаметной передачи разница между номерами столов не должна превышать `D`, т.е. записка может быть переброшена со стола `i` на стол `j` только если `|i-j|\ ≤\ D` и за обоими столами сидят студенты.
Для успешной передачи сообщений Петя может пригласить на помощь еще несколько студентов, чтобы они сели за пустующие столы. Нужно определить минимальное количество студентов, которых нужно посадить за пустующие столы для незаметной передачи сообщений.
Первая строка ввода содержит два целых числа `N` (`2\ ≤\ N\ ≤\ 300\ 000`) и `D` (`1\ ≤\ D\ <\ N`). Вторая строка содержит `N` целых чисел от 0 до 1. Число 1 соответствует столу, за которым сидит студент, а число 0 – пустому столу.
Вывести одно целое число – минимальное количество дополнительных студентов для незаметной передачи сообщений.

Пример ввода 1

4 1
1 0 1 1

Вывод для примера 1

1

Пример ввода 2

5 2
1 0 0 0 1

Вывод для примера 2

1

Пример ввода 3

8 2
1 1 0 0 1 0 0 1

Вывод для примера 3

2
loading