Submission #674842

#	Time	Username	Problem	Language	Result	Execution time	Memory
674842		benjaminkleyn	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	729 ms	288184 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
typedef long long ll;
ll delivery(int n, int k, int l, int p[]) 
{
    sort(p, p + n);

    vector<ll> pref(n + 1, 0);
    for (int i = 1; i <= k; i++)
        pref[i] = p[i-1];
    for (int i = k + 1; i <= n; i++)
        pref[i] = p[i-1] + pref[i - k];

    vector<ll> suff(n + 2, 0);
    for (int i = n; i > n - k; i--)
        suff[i] = (l - p[i-1]);
    for (int i = n - k; i >= 1; i--)
        suff[i] = (l - p[i-1]) + suff[i + k];

    ll ans = LLONG_MAX;
    for (int i = 1; i + k - 1 <= n; i++)
        ans = min(ans, l + 2 * pref[i - 1] + 2 * suff[i + k]);
    for (int i = 1; i <= n + 1; i++)
        ans = min(ans, 2 * pref[i - 1] + 2 * suff[i]);

    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