제출 #1009775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009775		ProtonDecay314	선물상자 (IOI15_boxes)	C++17	35 / 100	15 ms	504 KiB

boxes

/*
0 1l 2l 3l 4
1r 2r 3r

0
1l
2l = 1
3l = 2
4 = ?
1r
2r = 1
3r = 2
[3r, 3r, 3l] -> 8
[3l, 2l, 2r] -> 8
= 16

[3r, 3r, 2r] -> 6 
[3l, 3l, 2l] -> 6

1l, 2l, 3r

3l 3r 2r 2l 2l

[3l, 3r], [2l, 2l], [2r, 0l]
8 + 4 + 4 = 12

[3r, 2r], [3l, 2l], [2l, 0l]
6 + 6 + 4 = 16


*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
#define first fi;
#define second se;

vll facts = {1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll};

ll solve_kn(ll n, ll l, const vll& pos) {
    if(n == 0ll) return 0ll;
    ll max_left = 0ll;
    ll max_right = l;
    for(ll i = 0; i < n; i++) {
        if(pos[i] > (l >> 1ll) || ((l & 1) == 0ll && pos[i] == (l >> 1ll))) max_right = min(max_right, pos[i]);
        if(l - pos[i] > (l >> 1ll)) max_left = max(max_left, pos[i]);
    }

    return min(l, (l - max_right + max_left) << 1ll);
}

ll delivery(int intn, int intk, int intl, int pos_int[]) {
    ll n = intn, k = intk, l = intl;
    vll posl;
    vll posr;
    for(ll i = 0; i < n; i++) {
        if(pos_int[i] > (l >> 1ll)) posr.push_back(pos_int[i]);
        else posl.push_back(pos_int[i]);
    }
    
    ll ans = numeric_limits<ll>::max(), cost = 0ll;
    ll num_groups = (n - 1ll) / k + 1ll;

    sort(posl.begin(), posl.end());
    sort(posr.begin(), posr.end(), greater<ll>());
    

    for(ll num_circ = 0ll; num_circ <= num_groups; num_circ++) {
        cost = 0ll;
        ll lp = posl.size() - 1ll, rp = posr.size() - 1ll;
        for(ll i = 0ll; i < num_circ; i++) {
            vll group;

            for(ll j = 0ll; j < k && (lp >= 0ll || rp >= 0ll); j++) {
                if(lp >= 0ll && rp >= 0ll){
                    if(posl[lp] >= posr[rp]) {
                        group.push_back(posl[lp]);
                        lp--;
                    } else {
                        group.push_back(posr[rp]);
                        rp--;
                    }
                } else if(lp >= 0ll) {
                    group.push_back(posl[lp]);
                    lp--;
                } else {
                    group.push_back(posr[rp]);
                    rp--;
                }
            }

            cost += solve_kn(group.size(), l, group);
        }

        vll group;
        while(lp >= 0ll) {
            group.push_back(posl[lp]);
            lp--;
            if((ll)group.size() == k) {
                cost += solve_kn(group.size(), l, group);
                group.clear();
            }
        }
        cost += solve_kn(group.size(), l, group);
        group.clear();

        while(rp >= 0ll) {
            group.push_back(posr[rp]);
            rp--;
            if((ll)group.size() == k) {
                cost += solve_kn(group.size(), l, group);
                group.clear();
            }
        }
        cost += solve_kn(group.size(), l, group);

        ans = min(ans, cost);
    }

    return ans;
}

#ifdef DEBUG
int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, k, l;
    cin >> n >> k >> l;

    vi positions(n, 0);
    for(int& pos : positions) {
        cin >> pos;
    }

    cout << delivery(n, k, l, &positions[0]) << endl;
}
#endif

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