Задача Доставка

Question

Задача Доставка

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

C. Доставка

Ограничение времени 1 секунда
Ограничение памяти 256M
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt

Евгений — логист, и у него есть n товаров. За продажу i-го товара компания получит a_i монет прибыли (она может быть и отрицательной). В стране, в которой живет Евгений, странные правила выбора товаров для доставки: Евгений может выбрать любой отрезок товаров, но только один, и доставить все товары на этом отрезке (отрезком называется непрерывная последовательность товаров). Для доставки нужны грузовики, в каждый из которых помещается не более k любых товаров, причем за использование каждого грузовика нужно заплатить s монет. Найдите, какое максимальное количество монет может получить Евгений, учитывая затраты на грузовики.

Формат ввода

Первая строка содержит три целых числа n, k и s (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10, 1 ≤ s ≤ 10⁹) — количество товаров, а также числа k и s.

Вторая строка содержит n целых чисел a₁, a₂,…,a_n (-10⁹ ≤ a_i ≤ 10⁹) — стоимости товаров.

Формат вывода

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

Пример 1

Ввод

6 3 10
0 -4 16 -7 3 8

Вывод

Пример 2

Ввод

3 2 10
9 9 9

Вывод

Пример 3

Ввод

5 3 15
3 2 4 5 1

Вывод

Пример 4

Ввод

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

Вывод

Код на 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 секунды?

python c# олимпиада

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

Answer 1

▲ 1

Пусть p_i - максимальная прибыль для отрезка товаров завершающегося на позиции i. Тогда:

p_i ≥ 0 - отрезок может быть и пустым;
p_i ≥ ∑(a_j, ..., a_i) - s, где i - k < j ≤ i - можно отправить один грузовик полный или не полный;
p_i ≥ p_i-k + (∑(a_i-k+1, ..., a_i) - s), i ≥ k - можно отправить полный грузовик (второе слагаемое) и вместе с ним ещё сколько-то грузовиков перед ним (первое слагаемое).

Список выше исчерпывает все варианты значений для p_i. В каждой позиции 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, если применить кучу для поиска максимума в неполном грузовике.

Задача Доставка

Ответы