| Муниципальный этап ВсОШ по информатике 2026, 9-11 классы, Вологодская область и Краснодарский край |
|---|
| Закончено |
Бабушка хранит варенье в длинной ёмкости, разделённой на $$$N$$$ последовательных секций. В секции с номером $$$i$$$ находится $$$a_i$$$ единиц варенья.
Бабушка выбирает непустой участок из подряд идущих секций — с $$$i$$$-й по $$$j$$$-ю включительно — и сливает из него всё варенье в банки (она выполняет это один раз). Границами участка могут служить перегородки между секциями или края ёмкости.
Объём одной банки равен $$$M$$$. Бабушка заполняет только целые банки, а варенье, которого не хватило на следующую полную банку, выбрасывает.
Найдите минимальное количество варенья, которое придётся выбросить.
В первой строке записаны два целых числа $$$N$$$ и $$$M$$$ ($$$1 \le N \le 2\,000\,000$$$, $$$N \lt M \le 10\,000\,001$$$).
Во второй строке записаны $$$N$$$ целых чисел $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \le a_i \le 10^9$$$).
Выведите одно целое число — минимальное количество выброшенного варенья.
Подзадача 1 (до 30 баллов): $$$N \le 2\,000$$$.
Подзадача 2 (до 30 баллов): $$$N \le 200\,000$$$.
Подзадача 3 (до 40 баллов): без дополнительных ограничений.
3 105 8 6
3
1 22
0
1 100000011000000000
9999901
В задачу были добавлены дополнительные тесты, которых не было во время олимпиады.
Примечание для пишущих на Python. Набор целых чисел, записанных через пробел, можно прочитать так:
a = [int(x) for x in input().split()]
Примечание по быстрому вводу. В последней подзадаче нужно вводить большой объём данных. В некоторых языках для этого нужно использовать специальные способы ускорения ввода.
В языке C++ достаточно добавить в начало функции main следующие строки:
ios_base::sync_with_stdio(false);
cin.tie(0);
В Java используйте 'BufferedInputStream' и считывайте целые числа из байтов. 'Scanner' на большом входе может работать слишком медленно.
В C# используйте 'BufferedStream' поверх 'Console.OpenStandardInput()' и считывайте целые числа из байтов. Чтение всей строки через 'Console.ReadLine().Split()' создаёт много строк и может потребовать слишком много времени и памяти.
Пишущим на языке Python рекомендуется сдавать эту задачу на PyPy.
| Название |
|---|


