Решение задачи Тренировка Поликарпа с Codeforces

Поликарп тренирует свое умение решать задачи. У него есть список из n задач со сложностями a1,a2,…,an соответственно. Его план состоит в том, чтобы тренироваться ровно k дней. Каждый день он должен решать хотя бы одну задачу из своего списка. Поликарп решает задачи в том порядке, в котором они заданы в списке, и он не может пропустить какую-либо задачу из списка. Он должен решить ровно n задач ровно за k дней.

Таким образом, каждый день Поликарп решает последовательность подряд идущих (последовательных) задач с самого начала списка. Он не может пропускать задачи или решать их несколько раз. В итоге за k дней он решит n задач.

Полезность j-го дня тренировки Поликарпа равна максимальной сложности задачи среди всех задач, которые Поликарп решит в течение j-го дня (то есть если он решит задачи с номерами от l до r в течение какого-то дня, тогда полезность этого дня равна maxl≤i≤rai). Общая полезность его тренировки — это сумма полезностей по всем k дням его тренировки.

Вы хотите помочь Поликарпу получить максимально возможную общую полезность среди всех доступных способов решить задачи. Ваша задача — распределить n задач по k дням таким образом, что это распределение удовлетворяет ограничениям, описанным выше, и общая полезность является максимально возможной.

Например, если n=8,k=3 и a=[5,4,2,6,5,1,9,2], одним из возможных способов с максимальной общей полезностью является следующий: [5,4,2],[6,5],[1,9,2]. Здесь общая полезность равна 5+6+9=20.