Республиканская олимпиада по информатике. 2018 год

Задача F. Тренерский выбор Тимы

Ограничение по времени:

4 секунды

Ограничение по памяти:

256 мегабайт

Тима с недавних пор начал тренировать баскетбольные команды. Капитаном команды всегда выбирается игрок с максимальным ростом. Также он придумал свою формулу несовместимости игроков в одной команде. Формула зависит от роста всех игроков в команде. Несовместимость игроков в одной команде равняется сумме разниц роста между всеми игроками и ростом капитана. Более формально, пусть $h_1, h_2, ... , h_m$ это рост игроков команды, $mx = max(h_1, h_2, ..., h_m)$, тогда несовместимость = $\sum_{i=1}^{m} mx$-$h_i$. У Тимы есть $n$ игроков выстроенных в ряд, $i$-й из них имеет рост $a_i$. Он хочет разбить всех на $k$ команд, каждый игрок должен быть в ровно одной команде и команда должна состоять из игроков, которые составляют непрерывный отрезок в ряду. Тима хочет собрать команды так, чтобы суммарная несовместимость была минимальной. Помогите Тиме разбить на команды оптимально.

Формат входного файла

Первая строка входных данных содержит два целых чисел $n$ и $k$ ($1 \le n \le 10^5$, $1 \le k \le min(n, 20)$) — количество игроков в ряду и количество команд. Вторая строка содержит $n$ целых чисел $a_i$ ($1 \le a_i \le 10^6$) — рост $i$-го игрока слева в ряду в сантиметрах.

Формат выходного файла

Выведите единственное целое число — ответ на задачу.

Система оценки

Данная задача содержит шесть подзадач, в каждой подзадаче выполняются ограничения из условий:

1. $n \le 100$, $k = 1$. Оценивается в $5$ баллов.
2. $n \le 2000$. Оценивается в $11$ баллов.
3. $k = 2$. Оценивается в $8$ баллов.
4. $k = 3$. Оценивается в $15$ баллов.
5. $a_i \le a_{i+1}$, для всех $1 \le i < n$. Оценивается в $19$ баллов.
6. Ограничения из условия задачи. Оценивается в $42$ баллов.

Пример:

Вход

7 3
6 4 1 5 3 2 2

Ответ

7

Вход

5 2
4 1 5 5 6

Ответ

5

Вход

9 2
3 7 4 1 3 2 4 6 7

Ответ

22

( Temirlan Satylkhanov )