Задача Доставка
C. Доставка
Ограничение времени 1 секунда
Ограничение памяти 256M
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Евгений — логист, и у него есть 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
Код на Python:
n, k, s = map(int, input().split())
a = list(map(int, input().split()))
max_profit = 0
for i in range(n):
for j in range(i, n):
profit = sum(a[i:j+1])
if profit > 0:
trucks = (j - i + 1 + k - 1) // k
cost = trucks * s
max_profit = max(max_profit, profit - cost)
print(max_profit)
Код на C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, k, s;
cin >> n >> k >> s;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int max_profit = 0;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
int profit = 0;
for (int l = i; l <= j; l++)
profit += a[l];
if (profit > 0)
{
int trucks = (j - i + 1 + k - 1) / k;
int cost = trucks * s;
max_profit = max(max_profit, profit - cost);
}
}
}
cout << max_profit << endl;
return 0;
}
Задача решена верно, но тут ограничение времени в 1 секунду. И я не понимая как мне ещё можно оптимизировать код на Python. Решил переписать на C++ но вот все результаты:
Кто знает как добиться 1 секунды?
Ответы (1 шт):
Пусть pi - максимальная прибыль для отрезка товаров завершающегося на позиции i. Тогда:
- pi ≥ 0 - отрезок может быть и пустым;
- pi ≥ ∑(aj, ..., ai) - s, где i - k < j ≤ i - можно отправить один грузовик полный или не полный;
- pi ≥ pi-k + (∑(ai-k+1, ..., ai) - s), i ≥ k - можно отправить полный грузовик (второе слагаемое) и вместе с ним ещё сколько-то грузовиков перед ним (первое слагаемое).
Список выше исчерпывает все варианты значений для pi. В каждой позиции i нужно вычислить максимум из k + 2 значений.
def max_truck(b, s):
def acc():
yield 0
sum_ = 0
for v in reversed(b):
sum_ += v
yield sum_ - s
return max(acc())
def main():
n, k, s = map(int, input().split())
a = list(map(int, input().split()))
profit = [0] * (n + 1)
for i in range(k):
profit[i] = max_truck(a[:i], s)
for i in range(k, n + 1):
b = a[i - k:i]
profit[i] = max(max_truck(b, s), sum(b) - s + profit[i - k])
print(max(profit))
main()
Код имеет сложность nk. Так как k не велико, этого может хватить для решения задачи. Если нет, то сложность можно понизить до n·log k, если применить кучу для поиска максимума в неполном грузовике.