Submission #1198689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198689		Gr1sen	Boxes with souvenirs (IOI15_boxes)	C++20	0 / 100	11 ms	324 KiB

boxes

#include "boxes.h"
#include<algorithm>
#include<iomanip>
#include<vector>
#include<set>
#include<iterator>
#include<iostream>

using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define ms multiset<int>

ms M;
int glt, grt;
int k, n, l;
ll ans;

ll oink(int le = 1) {
    ans = 0;
    int lt = glt, rt = grt;
    auto it = M.begin();
    int re = n%k-le;
    if (le != 0) {
        advance(it, le-1);
        ans += 2*(*it);
        lt -= le;
        it++;
    }
    while (lt >= k) {
        advance(it, k-1);
        ans += 2*(*it);
        lt -= k;
        it++;
    }
    it = M.end();
    if (re != 0) {
        advance(it, -re);
        ans += 2*(*it);
        rt -= re;
    }
    while (rt >= k) {
        advance(it, -k);
        ans += 2*(l-(*it));
        rt -= k;
    }
    if (lt == 0 && rt == 0) return ans;
    //cerr << "oink ans : " << ans + l << endl;
    return ans + l;
}

ll oinkoink() {
    ans = 0;
    auto it = M.begin();
    advance(it, glt);
    auto it1 = it;
    it++;
    auto it2 = it;
    while (distance(M.begin(), it1) >= k) {
        ans += 2*(*it1);
        advance(it1, -k);
    }
    ans += 2*(*it1);
    while (distance(it2, M.end()) > k) {
        ans += 2*(*it2);
        advance(it2, -k);
    }
    ans += 2*(l-(*it2));
    return ans;
}

ll delivery(int in, int ik, int il, int p[]) {
    k = ik;
    n = in;
    l = il;
    ans = 0;
    M.clear();
    int lh = l/2;
    for (int i = 0; i < n; i++) {
        M.insert(p[i]);
        if (p[i] <= lh) glt++;
        else grt++;
    }
    ll best = oinkoink();
    //cerr << "best no circle : " << best << endl;
    for (int i = 1; i < k; i++) {
        best = min(best, oink(i));
        //cerr << "best: " << best << endl;
    }
    return best;
}

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