06/04/2025 20:12:58

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1593. Марсианские покупки

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

Юный марсианин Вася, живущий в Сидонии, много разговаривает по телефону и часто просит родителей пополнить его счёт. Родители, конечно, недовольны излишним расходом семейного бюджета. После долгого семейного совета был достигнут компромисс.

Васина семья составила список из

$N$ покупок, которые необходимо совершить в хронологическом порядке. Каждый день Васин папа может сделать от одной до

$K$ покупок – больше не вмещается в любимый семейный трипод. Васин папа педантичен и всегда старается, чтобы на счету его банковской карты была сумма, кратная

$M$ . Поэтому каждый день после совершения покупок он перечисляет на баланс Васиного телефона минимальную сумму, необходимую, чтобы остаток на карте стал кратен

$M$ .

Для каждой покупки известна стоимость

$C_i$ . Помогите папе распланировать покупки таким образом, чтобы после совершения всех

$N$ покупок суммарные затраты на Васин телефон оказались минимальными.

Входной файл содержит три целых числа –

$N\ K\ M$ (

$1\ ≤\ N\ ≤\ 40000$ ,

$1\ ≤\ K\ ≤\ 2000$ ,

$1\ ≤\ M\ ≤\ 10^4$ ), за которыми следуют

$N$ целых чисел

$C_i$ (

$1\ ≤\ C_i\ ≤\ 10^6$ ).

Выходной файл должен содержать единственное целое число – минимальные затраты на Васин телефон.

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

2 2 50
122 144

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

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

10 3 100
22 78 33 33 34 17 18 65 83 17

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

Во втором примере покупки лучше совершать следующим образом: в первый день – 2 покупки, во второй – 3, в третий – 3, в четвёртый – 2.

Источник: http://imcs.dvgu.ru/cats/ Весенний турнир, 2011

04/07/2011	Лето 2011 - дорешивание (03I)
06/07/2011	Лето 2011 - 3 (I)