Submission #1288116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288116		ortsac	Boxes with souvenirs (IOI15_boxes)	C++20	20 / 100	1 ms	584 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++) {
        pf[i] = pf[i - 1];
        if (((i - 1) % k) == 0) pf[i] += 2*v[i - 1];
    }
    for (int i = 1; i <= n; i++) pf[i] += v[i];
    // sf
    vector<int> sf(n + 2);
    for (int i = n; i >= 1; i--) {
        sf[i] = sf[i + 1];
        if (((n - i) % k) == 0) sf[i] += 2*(l - v[i + 1]);
    }
    for (int i = 1; i <= n; i++) sf[i] += (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]));
    }
    //cout << ans << "\n";
    return ans;
}

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