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

@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 часов, устал наверное, иди отдыхать.

Новые блоги и статьи Все статьи Все блоги /
Контроль уникальности заводского номера - вариант №2 Maks 24.03.2026 В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .
Контроль уникальности заводского номера - вариант №1 Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .

@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

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

Решение