Экономия центов
Для проведения регионального соревнования, такого как NWERC, необходимо приготовление: организация комнат и компьютеров, создание хорошего набора задач, приглашение конкурсантов, проектирование футболок, бронирование номеров в гостиницах и так далее. Я отвечаю за посещение магазина в супермаркете.
Когда я добираюсь до кассы, я кладу все свои n предметов на конвейер и жду, пока все остальные клиенты в очереди передо мной будут обслужены. Ожидая, я понимаю, что этот супермаркет недавно начал округлять общую цену покупки до ближайшего кратного в 10 центов (при 5 центах округление совершается вверх). Например 94 центов округлится до 90, в то время как 95 центов округлится до 100.
Можно разделить мои покупки на группы и отдельно их оплачивать. Мне удалось найти d разделителей, чтобы разделить покупки на d + 1 группу. Мне интересно, где разместить разделители, чтобы минимизировать общую стоимость всех покупок. Поскольку у меня заканчивается время, я не хочу переставлять предметы на ленте.
Входные данные
Состоит из:
строка содержит два числа n (1 ≤ n ≤ 2000) и d (1 ≤ d ≤ 20) - количество покупок и количество имеющихся в наличии разделителей;
строка из n целых чисел
p[1], ...,p[n](1 ≤p[i]≤ 10000 для 1 ≤ i ≤ n) - цены покупок в центах. Цены заданы в том же порядке в котором покупки размещены на ленте.
Выходные данные
Вывести наименьшее количество денег, необходимое для покупки всех продуктов, используя до d разделителей.