시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 5 | 1 | 1 | 33.333% |
Дед Мороз предлагает Вове выбрать подарки на Новый год.
Перед мальчиком лежат $n$ подарков в ряд. Каждый подарок характеризуется целым числом, у $i$-го подарка оно равно $a_i$ --- количество удовольствия, которое подарок принесёт Вове. Удовольствие может быть как положительным, так и отрицательным, а также равным нулю.
Дед Мороз предложил Вове выбрать два числа $l$ и $r$ таких, что $1 \le l \le r \le n$, и взять все подарки с номерами от $l$ до $r$. Однако $k$ подарков с максимальными характеристиками среди выбранных Вова должен отдать своей младшей сестре Маше. Остальные подарки Вова забирает себе.
Вова хочет выбрать числа $l$ и $r$ так, чтобы суммарное удовольствие от подарков, доставшихся именно ему, было максимальным. Общее удовольствие от набора подарков --- это сумма значений $a_i$ для подарков в наборе.
Помогите Вове выбрать числа $l$ и $r$ так, что $1 \le l \le r \le n$, $r - l + 1 \ge k$ и общее удовольствие от выбранных подарков без учёта подарков, доставшихся Маше, максимально.
В первой строке записаны два целых числа $n$ и $k$ ($1 \le n \le 200\,000$, $0 \le k \le \min(100, n)$) --- количество подарков перед Вовой и количество подарков, которые требуется отдать Маше.
Во второй строке заданы $n$ целых чисел через пробел $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) --- количество удовольствия, приносимого подарками.
Выведите единственное число --- общее удовольствие от выбранных Вовой подарков без учёта тех, что достались Маше.
번호 | 배점 | 제한 |
---|---|---|
1 | 7 | $n \le 200$ |
2 | 8 | $n \le 1000$ |
3 | 10 | $n \le 6000$ |
4 | 8 | $k = 0$ |
5 | 14 | $k = 1$ |
6 | 39 | $n \le 80\,000$ |
7 | 14 |
5 0 2 -4 5 -1 7
11
5 1 2 -4 5 -1 7
4
5 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$.
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2022 8번