Доставка

Евгений — логист, и у него есть n товаров. За продажу i-го товара компания получит ai монет прибыли (она может быть и отрицательной). В стране, в которой живет Евгений, странные правила выбора товаров для доставки: Евгений может выбрать любой отрезок товаров, но только один, и доставить все товары на этом отрезке (отрезком называется непрерывная последовательность товаров). Для доставки нужны грузовики, в каждый из которых помещается не более k любых товаров, причем за использование каждого грузовика нужно заплатить s монет. Найдите, какое максимальное количество монет может получить Евгений, учитывая затраты на грузовики.

Формат ввода

Первая строка содержит три целых числа n, k и s (1≤n≤105,1≤k≤10,1≤s≤109) — количество товаров, а также числа k и s.
Вторая строка содержит n целых чисел a1,a2,…,an (−109≤ai≤109) — стоимости товаров.

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

Выведите одно число — максимальное количество монет, которое может получить Евгений

Пример 1

Ввод:
6 3 10
0 -4 16 -7 3 8
Вывод:
6

Пример 2

Ввод:
3 2 10
9 9 9
Вывод:
8

Пример 3

Ввод:
5 3 15
3 2 4 5 1
Вывод:
0

Пример 4

Ввод:
10 3 5
-3 9 7 15 -10 9 7 6 -1 0
Вывод:
28

Примечания

В первом примере оптимально будет выбрать только товар со стоимостью 16 и потратить 10 монет на один грузовик.
Во втором примере оптимально выбрать любой отрезок из двух товаров.

В третьем примере не получится доставить ни одного товара так, чтобы получить прибыль.

В четвертом примере оптимально будет выбрать отрезок от второго товара до восьмого.

Добавлено через 1 час 9 минут
Я написал такой код:
n, k, s = (int(t) for t in input().split())
a = list(int(t) for t in input().split())

max_profit = 0
maxp = [0] * k
for i in range(k - 1):
m = min(k, i + 1)
maxp = [max(maxp[-1] + a[i], 0) - s] + [max(maxp[i - 1] + a[i], -s) for j in range(1, m)] + [0] * (k - m)
for i in range(k - 1, n):
maxp = [max(maxp[-1] + a[i], 0) - s] + [max(maxp[j - 1] + a[i], -s) for j in range(1, k)]
max_profit = max(*maxp, max_profit)

print(max_profit)
Всё равно пишет, что я неправильно написал.

0

Задача из олимпиады

0