| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 10 | 9 | 8 | 88.889% |
Правила новой телевизионной викторины следующие. В ряд расположены $n$ ячеек, пронумерованных от 1ドル$ до $n,ドル в $i$-й ячейке находится $a_i$ монет.
Игрок может выбрать целое число $b$ и заплатить $b$ монет. Тогда ведущий забирает монеты из всех ячеек, где лежит не более $b$ монет, соответствующие ячейки становятся пустыми. После этого среди любых $k$ подряд идущих ячеек должно быть не менее $m$ пустых. После этого игрок забирает все оставшиеся на поле монеты, если он забрал $a$ монет, его выигрыш составит $a-b$ монет.
Помогите игроку понять, какое максимальный выигрыш он может гарантировать.
На первой строке ввода находятся целые числа $n,ドル $k$ и $m$ (1ドル \le m < k \le n \le 200,000円$).
На второй строке находятся $n$ целых чисел $a_i$ (1ドル \le a_i \le 10^9$).
Выведите одно число: какой максимальной выигрыш может гарантировать себе игрок.
8 4 2 3 7 4 1 5 9 2 6
17
5 2 1 2 2 2 2 2
-2
В первом примере игрок выбирет $b = 5$. После удаления монет из ячеек, в которых лежит не более чем по 5ドル$ монет, количество монет в ячейках оказывается равно $[0, 7, 0, 0, 0, 9, 0, 6],ドル суммарно он забирает из ячеек 22ドル$ монеты, с учетом ранее отданных 5ドル$ монет выигрыш игрока составляет 17ドル$ монет.
Во втором примере, чтобы добиться, чтобы среди любых двух подряд идущих ячеек была хотя бы одна пустая, игроку приходится выбрать $b = 2$. После этого монет в ячейках нет, и выигрыш игрока оказывается отрицательным: $-2$.