Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 100 |
Дед Мороз предлагает Вове выбрать подарки на Новый год.
Перед мальчиком лежат n подарков в ряд. Каждый подарок характеризуется целым числом, у i-го подарка оно равно ai — количество удовольствия, которое подарок принесёт Вове. Удовольствие может быть как положительным, так и отрицательным, а также равным нулю.
Дед Мороз предложил Вове выбрать два числа l и r таких, что 1≤l≤r≤n, и взять все подарки с номерами от l до r. Однако k подарков с максимальными характеристиками среди выбранных Вова должен отдать своей младшей сестре Маше. Остальные подарки Вова забирает себе.
Вова хочет выбрать числа l и r так, чтобы суммарное удовольствие от подарков, доставшихся именно ему, было максимальным. Общее удовольствие от набора подарков — это сумма значений ai для подарков в наборе.
Помогите Вове выбрать числа l и r так, что 1≤l≤r≤n, r−l+1≥k и общее удовольствие от выбранных подарков без учёта подарков, доставшихся Маше, максимально.
В первой строке записаны два целых числа n и k (1≤n≤200000, 0≤k≤min) — количество подарков перед Вовой и количество подарков, которые требуется отдать Маше.
Во второй строке заданы 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 |
|
|
2 |
|
|
3 |
|
|