Submission #294371

#	Time	Username	Problem	Language	Result	Execution time	Memory
294371		peti1234	선물상자 (IOI15_boxes)	C++17	100 / 100	836 ms	255152 KiB

boxes

#include <bits/stdc++.h>

using namespace std;
const int c=10000002;
vector<int> a, b;
long long as, bs, ka[c], kb[c], mini=1e18;
//long long delivery(int n, int k, int l, vector<int> sz) {
long long delivery(int n, int k, int l, int sz[]) {
    for (int i=0; i<n; i++) {
        int x=sz[i];
        if (2*x<l) a.push_back(x);
        else b.push_back(l-x);
    }
    sort(a.begin(), a.end()), sort(b.begin(), b.end()), as=a.size(), bs=b.size();
    for (int i=0; i<as; i++) {
        ka[i+1]=2*a[i];
        if (i>=k) ka[i+1]+=ka[i-k+1];
    }
    for (int i=0; i<bs; i++) {
        kb[i+1]=2*b[i];
        if (i>=k) kb[i+1]+=kb[i-k+1];
    }
    if (n<k) mini=l;
    mini=min(mini, ka[as]+kb[bs]);
    for (int i=0; i<k; i++) if (as>=i && bs>=k-i) mini=min(mini, l+ka[as-i]+kb[bs-k+i]);
    return mini;
}

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