Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Подарки

(Время: 2 сек. Память: 64 Мб Сложность: 78%)

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

Перед мальчиком лежат 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 и общее удовольствие от выбранных подарков без учёта подарков, доставшихся Маше, максимально.

Входные данные

В первой строке входного файла INPUT.TXT записаны два целых числа n и k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ min(100, n)) – количество подарков перед Вовой и количество подарков, которые требуется отдать Маше.

Во второй строке заданы n целых чисел через пробел a1, a2, ... , an (−109 ≤ ai ≤ 109) – количество удовольствия, приносимого подарками.

Выходные данные

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

Примеры

INPUT.TXTOUTPUT.TXT
15 0
2 -4 5 -1 7
11
25 1
2 -4 5 -1 7
4
35 2
2 -4 5 -1 7
0

Пояснение

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

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

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


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 A. Чемпионат по устному счету
 B. Прыгающий робот
 C. Треугольная головоломка
 D. Массивы-палиндромы
 E. Новый год в детском саду
 F. Сортировка дробей
 G. Оптические каналы связи
 H. Подарки

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru