Submission #1038576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038576		HappyCapybara	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	680 ms	293796 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll delivery(int N, int K, int L, int p[]){
    int l = 0, r = 0;
    vector<ll> ld, rd;
    for (int i=0; i<N; i++){
        if (p[i] <= L/2){
            l++;
            ld.push_back(p[i]);
        }
        else {
            r++;
            rd.push_back(L-p[i]);
        }
    }
    sort(ld.begin(), ld.end());
    sort(rd.begin(), rd.end());
    /*for (int i=0; i<l; i++) cout << ld[i] << " ";
    cout << "\n";
    for (int i=0; i<r; i++) cout << rd[i] << " ";
    cout << "\n";*/

    vector<ll> lc(l+1, 0), rc(r+1, 0);
    for (int i=0; i<K; i++){
        if (i < l){
            int j = l-i-1;
            while (j >= 0){
                lc[l-i] += 2*ld[j];
                j -= K;
            }
        }
        if (i < r){
            int j = r-i-1;
            while (j >= 0){
                rc[r-i] += 2*rd[j];
                j -= K;
            }
        }
    }
    for (int i=l-K; i>=0; i--) lc[i] = lc[i+K] - 2*ld[i+K-1];
    for (int i=r-K; i>=0; i--) rc[i] = rc[i+K] - 2*rd[i+K-1];
    /*for (int i=0; i<=l; i++) cout << lc[i] << " ";
    cout << "\n";
    for (int i=0; i<=r; i++) cout << rc[i] << " ";
    cout << "\n";*/
    ll bsf = lc[l] + rc[r];
    ll cl = 0;
    if (K == 1) return bsf;
    while (l+r > 0){
        /*cout << l << " " << r << "\n";
        cout << bsf << "\n";
        if (bsf < 0) break;*/
        if (l+r <= K){
            l = 0;
            r = 0;
        }
        else {
            ll blr = lc[l] + rc[r];
            int bl = l, br = r;
            for (int i=0; i<=K; i++){
                //cout << blr << "\n";
                if (lc[max(l-i, 0)] + rc[max(r-(K-i), 0)] < blr){
                    blr = lc[max(l-i, 0)] + rc[max(r-(K-i), 0)];
                    bl = max(l-i, 0);
                    br = max(r-(K-i), 0);
                }
            }
            l = bl;
            r = br;
        }
        cl++;
        bsf = min(bsf, lc[l]+rc[r]+(ll)L*cl);
        break;
    }
    return bsf;
}

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