Submission #674846

#	Time	Username	Problem	Language	Result	Execution time	Memory
674846		benjaminkleyn	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	650 ms	239972 KiB

boxes

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,bmi,bmi2")
#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
typedef long long ll;

ll pref[10000010], suff[10000010];

ll delivery(int n, int k, int l, int p[]) 
{
    sort(p, p + n);

    memset(pref, 0, (n + 1) * sizeof(ll));

    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];

    memset(suff, 0, (n + 2) * sizeof(ll));

    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