Submission #127479

#	Time	Username	Problem	Language	Result	Execution time	Memory
127479		wasyl	Boxes with souvenirs (IOI15_boxes)	C++11	100 / 100	600 ms	208708 KiB

boxes

#include "boxes.h"

long long max(long long a, long long b)
{
    return (a > b)? a : b;
}

long long min(long long a, long long b)
{
    return (a < b)? a : b;
}

long long delivery(int n, int k, int l, int p[]) {
    static constexpr int nax = 1e7;
    static constexpr long long inf = 1e18;
    long long dp[nax + 2], pd[nax + 2];
    dp[0] = 0;
    for (int i = 1; i <= n; ++i)
        dp[i] = dp[max(0, i - k)] + p[i - 1] * 2ll;
    pd[n + 1] = 0;
    for (int i = n; i >= 1; --i)
        pd[i] = pd[min(n + 1, i + k)] + (l - p[i - 1]) * 2ll;
    long long res = inf;
    for (int i = 0; i <= n; ++i)
        res = min(res, dp[i] + pd[i + 1]);
    for (int i = 0; i < n; ++i)
    {
        int a = i - 1;
        int b = i + k;
        if (a < -1 or b > n) continue;
        res = min(res, l + dp[a + 1] + pd[b + 1]);
    }
    return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30