Processing math: 47%

Задача 4. Подарки

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Дед Мороз предлагает Вове выбрать подарки на Новый год.

Перед мальчиком лежат n подарков в ряд. Каждый подарок характеризуется целым числом, у i-го подарка оно равно ai — количество удовольствия, которое подарок принесёт Вове. Удовольствие может быть как положительным, так и отрицательным, а также равным нулю.

Дед Мороз предложил Вове выбрать два числа l и r таких, что 1lrn, и взять все подарки с номерами от l до r. Однако k подарков с максимальными характеристиками среди выбранных Вова должен отдать своей младшей сестре Маше. Остальные подарки Вова забирает себе.

Вова хочет выбрать числа l и r так, чтобы суммарное удовольствие от подарков, доставшихся именно ему, было максимальным. Общее удовольствие от набора подарков — это сумма значений ai для подарков в наборе.

Помогите Вове выбрать числа l и r так, что 1lrn, rl+1k и общее удовольствие от выбранных подарков без учёта подарков, доставшихся Маше, максимально.

Формат входных данных

В первой строке записаны два целых числа n и k (1n200000, 0kmin) — количество подарков перед Вовой и количество подарков, которые требуется отдать Маше.

Во второй строке заданы n целых чисел через пробел a_1,\,a_2, \ldots,\,a_n (-10^9 \le a_i \le 10^9) — количество удовольствия, приносимого подарками.

Формат выходных данных

Выведите единственное число — общее удовольствие от выбранных Вовой подарков без учёта тех, что достались Маше.

Ограничения

1 \le n \le 200\,000, 0 \le k \le \min(100,\,n)

-10^9 \le a_i \le 10^9

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
1 7 n \le 200 первая ошибка
2 8 n \le 1000 1 первая ошибка
3 10 n \le 6000 1, 2 первая ошибка
4 8 k = 0 первая ошибка
5 14 k = 1 первая ошибка
6 39 n \le 80\,000 1 — 3 первая ошибка
7 14 1 — 6 первая ошибка

Замечание

В первом примере Вова ничего не должен отдавать Маше, поэтому он выберет l = 3, r = 5, и общее удовольствие от выбранных подарков будет равняться 5 + (-1) + 7 = 11.

Во втором примере Вова должен будет отдать Маше подарок с самым большим количеством удовольствия. Тогда он так же выберет l = 3, r = 5, однако общее удовольствие будет равняться 5 + (-1) = 4.

В третьем примере Вова должен отдать два подарка с наибольшими характеристиками. В таком случае одним из оптимальных вариантов будет выбрать l = 1, r = 2.

Примеры тестов

Стандартный вход Стандартный выход
1
5 0
2 -4 5 -1 7
11
2
5 1
2 -4 5 -1 7
4
3
5 2
2 -4 5 -1 7
0

0.064s 0.010s 13