Submission #1288118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288118		ortsac	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	488 ms	274768 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;
    vector<int> v;
    v = {0};
    for (int i = 0; i < n; i++) v.push_back(p[i]);
    v.push_back(l);
    // ok
    vector<int> pf(n + 1); // how many extras
    for (int i = 1; i <= n; i++) {
        if (i < k) pf[i] = v[i];
        else pf[i] = (pf[i - k] + v[i - k] + v[i]);
    }
    // sf
    vector<int> sf(n + 2);
    for (int i = n; i >= 1; i--) {
        if ((i + k) > (n + 1)) sf[i] = (l - v[i]);
        else sf[i] = (sf[i + k] + (l - v[i + k]) + (l - v[i]));
    }
    // ok
    int ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = 0; i <= n; i++) {
        ans = min(ans, pf[i] + sf[i + 1] + dist(0, v[i]) + dist(0, v[i + 1]));
    }
    return ans;
}

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