Submission #1058997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058997		andrei_iorgulescu	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	400 ms	372040 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"

using namespace std;

using ll = long long;

ll inf = (ll)1e9 * (ll)1e9;

ll delivery(int N, int k, int L, int positions[])
{
    vector<int> p(N + 1);
    for (int i = 1; i <= N; i++)
        p[i] = positions[i - 1];
    ll ans = inf;
    vector<int> revp(N + 1);
    vector<ll> pref(N + 1), suf(N + 1);
    for (int i = 1; i <= N; i++)
        revp[i] = (L - p[i]);
    for (int i = 1; i <= N; i++)
    {
        pref[i] = min(L, 2 * p[i]) + pref[max(0, i - k)];
    }
    for (int i = N; i >= 1; i--)
    {
        suf[i] = min(L, 2 * revp[i]);
        if (i + k <= N)
            suf[i] += suf[i + k];
    }
    for (int m = 0; m <= N; m++)
    {
        ll kk = pref[m];
        if (m + 1 <= N)
            kk += suf[m + 1];
        ans = min(ans,kk);
    }
    return ans;
}

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