Submission #1288094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288094		ortsac	Boxes with souvenirs (IOI15_boxes)	C++20	10 / 100	1 ms	580 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

int n, k, l;

int dist(int a, int b) {
    if (a > b) swap(a, b);
    if (a == 0) return min(b, l - b);
    return min(b - a, dist(0, a) + dist(0, b));
}

int delivery(int32_t N, int32_t K, int32_t L, int32_t p[]) {
    n = N, k = K, l = L;
    map<int, int> pos;
    for (int i = 0; i < n; i++) pos[p[i]]++;
    deque<pii> v = {{0, 0}};
    for (auto [a, b] : pos) v.push_back({a, b});
    v.push_back({0, 0});
    int cval, ans, lst;
    deque<pii> bv = v;
    n = v.size(); 
    // run one
    cval = k, ans = 0;
    lst = 0;
    vector<int> pf(n);
    for (int i = 0; i < n; i++) {
        auto& [po, need] = v[i];
        ans += dist(lst, po);
        // get whatever is needed done in here
        while (need > cval) {
            need -= cval;
            ans += 2*dist(0, po);
            cval = k;
        }
        cval -= need;
        need = 0;
        pf[i] = ans;
        // go to next one
        lst = po;
    }
    // run 2
    v = bv;
    vector<int> sf(n);
    cval = k, ans = 0;
    lst = 0;
    for (int i = n - 1; i >= 0; i--) {
        auto& [po, need] = v[i];
        ans += dist(lst, po);
        // get whatever is needed done in here
        while (need > cval) {
            need -= cval;
            ans += 2*dist(0, po);
            cval = k;
        }
        cval -= need;
        need = 0;
        sf[i] = ans;
        // go to next one
        lst = po;
    }
    // calc ans
    int mians = min(pf[n - 1], sf[0]);
    for (int i = 0; i < n; i++) {
        if ((i + 1) < n) mians = min(mians, pf[i] + sf[i + 1] + dist(v[i].fr, 0) + dist(v[i + 1].fr, 0));
        if (i > 0) mians = min(mians, pf[i - 1] + sf[i] + dist(v[i].fr, 0) + dist(v[i - 1].fr, 0));
    }
    // print
    return mians;
}

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