Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2351. Передача сообщений
Жадные алгоритмыОлимпиадные задачи на русском языке
| 14/10/2017 | Открытые личные соревнования по спортивному программированию (C) |
| 04/07/2018 | Лето 2018 - 5 (упрощенное) (B) |
| 08/07/2019 | Лето 2019 - 4 (упрощенное) (D) |
| 08/07/2020 | Лето 2020 - 4 (упрощенное) (B) |
Ограничения: время – 500ms/1000ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
