Submission #127464

#	Time	Username	Problem	Language	Result	Execution time	Memory
127464		wasyl	Boxes with souvenirs (IOI15_boxes)	C++11	25 / 100	2 ms	376 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];
    int d = -1;
    while (d + 1 < n and p[d + 1] < l / 2) ++d;
    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;
    res = min(res, dp[d + 1] + pd[d + 2]);
    if (d + 1 < n) res = min(res, dp[d + 1 + 1] + pd[d + 1 + 2]);
    for (int i = 0; i <= k; ++i)
    {
        int nd = d - i;
        if (nd < -1) break;
        int dn = d + 1 + (k - i);
        if (dn > n + 1) continue;
        res = min(res, l + dp[nd + 1] + pd[dn + 1]);
    }
    return res;
}

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