2г

Превышение лимит времени. Как сделать скорость по меньше?

Я написал правильно код
примеры правильно выводит:

import math

n, k, s = map(int, input().split())
a = list(map(int, input().split()))
max_coins = 0
for i in range(n):
for j in range(i + 1, n + 1):
coins = sum(a[i:j]) - math.ceil(len(a[i:j]) / k) * s
if coins > max_coins:
max_coins = coins

print(max_coins)

Это из задачи:
Евгений — логист, и у него есть 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 монет на один грузовик.
Во втором примере оптимально выбрать любой отрезок из двух товаров.

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

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

Можете подсказать, как уменьшить скорость для времени, чтобы не так быстро выводил?

По дате

По Рейтингу

papa_1085

Новичок

2г

Снова Евгений-логист. Тебе же уже отвечали на этот вопрос. Используй алгоритм Кадане, модифицированный под штрафы. Он имеет сложность O(n*k). А то, что найденный тобой на просторах сети "понятный" быдлокод корректно работает на паре примеров, ещё не значит, что он пройдёт тест по времени на 10 тыс. чисел, т.к. его сложность O(n²).

Вот код, если что:

12345678910111213

 p, 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, p):
    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)

В принципе, тут и список 'a' не нужен, хватило бы итератора. Один проход. Тогда памяти бы меньше занимал (хотя, не факт, т.к. Питон может удерживать в памяти результат input().split(), пока всё не обработается).

123456789101112131415

 p, k, s = (int(t) for t in input().split())
a = (int(t) for t in input().split())

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

print(max_profit)

user49913

Просветленный

2г

пусть f[i] - максимальная прибыль, которую можно получить со всех отрезков, заканчивающихся в позиции i (не включительно)
тогда f[i] = max(f[i - k] + sum(a[i-k:i]) - s, sum(a[i-k+1..i]) - s, ..., sum(a[i-1..i]) - s)
ответ - max(f)
сложность O(nk)
у твоего сложность где-то O(n^3), поэтому он и не проходит