3-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Задача A. Разделение команды

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

1 секунда

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

256 мегабайт

Есть $n$ игроков которые стоят в ряд. Они хотят сыграть в игру. Для этого им нужно разделится на две команды по $k$ человек. У $i$-го игрока $a_i$ уровень игры. Сила команды это сумма уровней всех его участников. Вы можете выбрать $2 * k$ игроков которые будут играть. Но они сами поделятся на команды. В первой команде будут первые $k$ игроков которые стоят ближе к началу ряду. Во второй команде будут последние $k$ игроков. Запишем силу первой команды как $A$ и второй как $B$. Найдите максимальное значение $A - B$. Например, есть $6$ игроков с уровнями $[3, 1, 7, 2, 1, 2]$. Если выбрать игроков с номерами $1, 3, 5 ,6$ то в первой команде будут игроки $1, 3$ и сила команды $A = 3 + 7 = 10$, во второй игроки $5, 6$ и сила команды $B = 1 + 2 = 3$. $A - B = 10 - 3 = 7$.

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

В первой строке два целых числа $n$, $k$ ($1 <= n <= 10^5$, $1 <= k <= \frac{n}{2}$) - колчество игроков и размер команд. Во второй строке $n$ целых чисел $a_1, a_2 \ldots a_n$ ($1 <= a_i <= 10^5$) - уровень игроков.

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

Выведите максимальное значение $A - B$.

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

Данная задача содержит $7$ подзадач, в которых выполняются следующие ограничения:

1. $n <= 15$. Оценивается в $12$ баллов.
2. $a_i \geq a_{i+1}$ для $1 <= i <= n - 1$. Оценивается в $11$ баллов.
3. $a_i <= a_{i+1}$ для $1 <= i <= n - 1$. Оценивается в $11$ баллов.
4. $k = 1$. Оценивается в $16$ баллов.
5. $k <= 100$. Оценивается в $19$ баллов. Необходимые подзадачи: 4.
6. Исходные условия задачи. Оценивается в $31$ баллов. Необходимые подзадачи: 1,2,3,4,5.

Примеры:

Вход

6 2
3 1 7 2 1 2

Ответ

7

Вход

5 1
3 4 6 8 9

Ответ

-1

( Batyr Sardarbekov )