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

@fhsfdghtfr · Регистрация: 04.03.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

Примечания

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

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

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

Я что то попытался сделать, но там с некоторыми примерами не сходится.

не совпадает 2 и 4 примеры.
во 2 примере выходит 0 вместо 8.
в 4 примере выходит 23 вместо 28.
Вообще уже 2 дня сижу над ней.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
n, k, s = map(int, input().split())
a = list(map(int, input().split()))
 
dp = [0] * (n+1)
for i in range(1, n+1):
    for j in range(i, max(1, i-k)-1, -1):
        cost = sum(a[j-1:i]) - s * (i-j+1)
        if cost > 0:
            dp[i] = max(dp[i], dp[j-1] + cost)
        else:
            dp[i] = max(dp[i], dp[j-1])
 
print(dp[n])

@eaa · 09.04.2023, 16:24

fhsfdghtfr, почему ты решил, что тут дп?

10 3 5
-3 9 7 15 -10 9 7 6 -1 0

1ая машина (9+7+15-5)=26
2ая машина (-10-5) = -15
3ая машина (9+7+6-5) = 17

итого: 26-15+17 = 28

@Berbentsev · 09.04.2023, 16:27

Сообщение от fhsfdghtfr

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

по такой логике получается можно взять 16-10 и 3+8-10, что-то в задании не так.

@eaa · 09.04.2023, 16:29

Berbentsev, а куда -7 потерялся?

@Berbentsev · 09.04.2023, 16:29

Не, не прав. извиняюсь. Отрезок же непрерывный.

@fhsfdghtfr · 09.04.2023, 16:30 **[ТС]**

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

@eaa · 09.04.2023, 16:34

10 3 5
-3 9 7 15 -10 9 7 6 -1 0

1ая машина (9+7+15-5)=26
2ая машина (-10+9+7-5) = 1
3ая машина (6-5) = 1

итого: 26+1+1 = 28

вот так правильней будет.

@fhsfdghtfr · 09.04.2023, 16:40 **[ТС]**

всё равно ничего не понимаю...
пойду уроки лучше делать)
потом буду думать над задачей, все равно тупой для того чтобы код писать

@eaa · 09.04.2023, 16:48

fhsfdghtfr, вот почитай.
Поиск подотрезка массива с максимальной/минимальной суммой

Добавлено через 1 минуту
только у тебя тут есть еще K и S

@Berbentsev · 09.04.2023, 17:01

Python
1
2
3
4
5
6
7
8
9
10
11
12
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)

@eaa · 09.04.2023, 17:14

Berbentsev, это O(n^3), по времени не пройдет.

Сообщение от Berbentsev

math.ceil(len(a[i:j]) / k)*s

и эта конструкция "порадовала")

@fhsfdghtfr · 09.04.2023, 17:15 **[ТС]**

тест по времени не проходит, но спасибо!
9 апр 2023, 19:12:44
85472584
C
Python 3.9 (PyPy 7.3.11)
TL
-
1.095s
110.64Mb
12 -
отчёт

@papa78191 · 09.04.2023, 17:17

Теперь пишет, что лимит времени превышен

@eaa · 09.04.2023, 17:24

можно сократить время до O(n^2) если предварительно подсчитать префикс-суммы.

@Berbentsev · 09.04.2023, 17:40

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import math
 
n, k, s = map(int, input().split())
a = list(map(int, input().split()))
max_coins = 0
for i in range(n):
    sum_coins = 0
    for j in range(i+1, n):
        sum_coins += a[j]
        coins = sum_coins - math.ceil((j-i) / k) * s
        if coins > max_coins:
            max_coins = coins
 
print(max_coins)

@eaa · 09.04.2023, 17:46

Сообщение от Berbentsev

j-i

+1 еще видимо. нет?

@papa78191 · 09.04.2023, 17:54

Пишет, что неверный ответ

@Berbentsev · 09.04.2023, 21:30

Сообщение от eaa

+1 еще видимо. нет?

Да вроде нет, j всегда больше i

Добавлено через 3 часа 24 минуты

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import math
 
n, k, s = map(int, input().split())
a = list(map(int, input().split()))
max_coins = 0
sum_coins = 0
number = 0
for value in a:
    if value <= 0 and sum_coins == 0:
        continue
    sum_coins += value
    number += 1
    coins = sum_coins - math.ceil(number / k) * s
    if coins <= 0 and number > 1:
        sum_coins = 0
        number = 0
        continue
    if coins >= max_coins:
        max_coins = coins
 
print(max_coins)

Вот еще набросал. Наверное быстрее должно работать.

@fhsfdghtfr · 09.04.2023, 22:02 **[ТС]**

Емаё. На 10 тесте ошибка WA. Спасибо, но ложись спать, поздно.

Добавлено через 4 минуты
Реально. Ты здесь уже 8 часов, устал наверное, иди отдыхать.

Новые блоги и статьи Все статьи Все блоги /
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.04.2023, 16:24
	fhsfdghtfr, почему ты решил, что тут дп? 10 3 5 -3 9 7 15 -10 9 7 6 -1 0 1ая машина (9+7+15-5)=26 2ая машина (-10-5) = -15 3ая машина (9+7+6-5) = 17 итого: 26-15+17 = 28 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.04.2023, 16:29
	Berbentsev, а куда -7 потерялся? 0

@Berbentsev 290 / 170 / 92 Регистрация: 21.03.2016 Сообщений: 400
	09.04.2023, 16:29
	Не, не прав. извиняюсь. Отрезок же непрерывный. 1

@fhsfdghtfr 0 / 0 / 0 Регистрация: 04.03.2023 Сообщений: 5
	09.04.2023, 16:30 [ТС]
	мы командой решаем, никто ничего не понимает и я тоже, вот решил тут спросить 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.04.2023, 16:34
	10 3 5 -3 9 7 15 -10 9 7 6 -1 0 1ая машина (9+7+15-5)=26 2ая машина (-10+9+7-5) = 1 3ая машина (6-5) = 1 итого: 26+1+1 = 28 вот так правильней будет. 1

@fhsfdghtfr 0 / 0 / 0 Регистрация: 04.03.2023 Сообщений: 5
	09.04.2023, 16:40 [ТС]
	всё равно ничего не понимаю... пойду уроки лучше делать) потом буду думать над задачей, все равно тупой для того чтобы код писать 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.04.2023, 16:48
	fhsfdghtfr, вот почитай. Поиск подотрезка массива с максимальной/минимальной суммой Добавлено через 1 минуту только у тебя тут есть еще K и S 1

@fhsfdghtfr 0 / 0 / 0 Регистрация: 04.03.2023 Сообщений: 5
	09.04.2023, 17:15 [ТС]
	тест по времени не проходит, но спасибо! 9 апр 2023, 19:12:44 85472584 C Python 3.9 (PyPy 7.3.11) TL - 1.095s 110.64Mb 12 - отчёт 0

@papa78191 0 / 0 / 0 Регистрация: 31.10.2022 Сообщений: 30
	09.04.2023, 17:17
	Теперь пишет, что лимит времени превышен 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.04.2023, 17:24
	можно сократить время до O(n^2) если предварительно подсчитать префикс-суммы. 1

@papa78191 0 / 0 / 0 Регистрация: 31.10.2022 Сообщений: 30
	09.04.2023, 17:54
	Пишет, что неверный ответ 0

@fhsfdghtfr 0 / 0 / 0 Регистрация: 04.03.2023 Сообщений: 5
	09.04.2023, 22:02 [ТС]
	Емаё. На 10 тесте ошибка WA. Спасибо, но ложись спать, поздно. Добавлено через 4 минуты Реально. Ты здесь уже 8 часов, устал наверное, иди отдыхать. 0

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

Решение