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

Задача A. Топтық ойын

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

1 second

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

256 megabytes

Бір күні $n$ адам ойын ойнамақшы болып шешті. Ойынды бастау үшін олар екі топқа бөлінулері керек. Әр $i$-інші ойыншының ойнау қабілеті $a_i$. Топтың күші сол топтағы ойыншылардың қабілеттерінің қосындысы. Сізге ойнайтын $2 * k$ адамды таңдау керек. Олар өзара екі топқа бөлінеді. Бірінші топта қатардың басына жақын $k$ ойыншы болады. Екінші топта қатардың соңына жақын $k$ ойыншы болады. Бірінші топтың күшін $A$, ал екінші топтың күшін $B$ деп алайық. Ең үлкен $A - B$ нәтижесін табыңыз. Мысалы, ойнау қабілеттері $[3, 1, 7, 2, 1, 2]$ болатын $6$ адам бар. Позициялары $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$ мәнін табыңыз.

Примеры:

Вход

6 2
3 1 7 2 1 2

Ответ

7

Вход

5 1
3 4 6 8 9

Ответ

-1

Түсініктеме

Бұл есеп $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 бөліктері шығарылған болу керек.

( Batyr Sardarbekov )