| Автор: | А. Саранцев, И. Ланцов, А. Лепёха | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Кирилл приехал с друзьями отдыхать на тропический курорт. Прибыв в отель, они увидели N бассейнов одинакового размера, которые были расположены в ряд. К сожалению, водой были наполнены лишь K бассейнов. Увидев бассейны, Кирилл решил во что бы то ни стало провести бассейную вечеринку.
Для бассейной вечеринки нужно, чтобы все бассейны с водой были расположены рядом друг с другом (между каждыми двумя наполненными бассейнами не должно быть бассейнов без воды). Чтобы достичь этого, друзья могут перелить воду из любого наполненного бассейна в любой из двух соседних, если соседний не наполнен. Какое минимальное количество переливаний воды из бассейна в бассейн Кириллу и друзьям понадобится сделать, чтобы все было готово к вечеринке?
Первая строка входных данных содержит целые числа N К, где N — общее количество бассейнов, K — количество бассейнов, наполненных водой.
Вторая строка входных данных содержит строку S, состоящую из N символов 0 и 1. Si = 1, если бассейн на позиции i наполнен, Si = 0 в противном случае.
Гарантируется, что S содержит ровно K единиц.
Требуется вывести целое число — минимальное количество переливаний.
1 ≤ K ≤ N ≤ 1000000
Решение оценивается пропорционально количеству успешно пройденных тестов.
| Подзадача | Баллы |
|---|---|
| 1 ≤ N ≤ 10, 1 ≤ K ≤ 3 | 20 |
| 1 ≤ N ≤ 1000, 1 ≤ K ≤ 1000 | 30 |
| 1 ≤ N ≤ 1000000, 1 ≤ K ≤ 1000000 | 50 |
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|