Доставка помогите пожалуйста есть решение, но нужно сложность сделать n*k

Question

Доставка помогите пожалуйста есть решение, но нужно сложность сделать n*k

Рейтинг: -3Ответов: 1Опубликовано: 10.04.2023

Евгений — логист, и у него есть 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

мое решение

n, k, s = map(int, input().split())
a = []
x = 0
r = True
for i in list(map(int, input().split())):
    if i < 0 and r:
        continue
    if i > 0 and r:
        r = False
    a.append(i)


for i in range(len(a)):
    for j in range(len(a), i, -1):
        d = sum(a[i: j]) - (((j - i - 1) // k + 1) * s)
        if d > x:
            x = d
print(max(x, max(a) - s))

python c#

Источник: Stack Overflow на русском

Answer 1

▲ 1

n, k, s = map(int, input().split())

a = list(map(int, input().split()))

ans = 0
for i in range(k):
    cur = 0
    min_prefix = 0
    for j in range(i, n):
        if j % k == i:
            min_prefix = min(min_prefix, cur)
            cur += a[j] - s
        else:
            cur += a[j]
        ans = max(ans, cur - min_prefix)


print(ans)

Доставка помогите пожалуйста есть решение, но нужно сложность сделать n*k

Ответы