Решение задач «Python»,
Программирование в Нижнем Новгороде

Вася решил питаться рыбой. Он решил, что в течение N дней он должен съедать по одной рыбе каждый день. К сожалению, рыба — товар скоропортящийся и может храниться не более K дней, включая день покупки. С помощью методов машинного обучения Вася предсказал цены на рыбу на N дней вперёд. Помогите Васе определить, в какие дни и сколько рыбы нужно покупать, чтобы потратить как можно меньше денег. Формат ввода В первой строке вводится два целых числа N и K (1 ? N, K ? 100?000) — количество дней, в течение которых нужно питаться рыбой, и срок хранения рыбы соответственно. Во второй строке вводится N чисел, разделенных пробелами: стоимость рыбы в этот день Ci (1 ? Ci ? 106). Формат вывода В первой строке выведите минимальную сумму, потраченную на рыбу. Во второй строке выведите N чисел — количество купленных рыб в каждый из дней. Если правильных ответов несколько — выведите любой из них. Примечания В первом примере K = 1, т.е. рыбу нужно есть в день покупки. Во втором примере Вася покупает одну рыбу в первый день за 3 рубля и две рыбы во второй день по 1 рублю каждая. На третий день он ест рыбу, купленную во второй день, т.к. K = 2 и её срок годности еще не истек.