Submission #1191662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191662		gelov	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	787 ms	232136 KiB

boxes

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

vector<ll> forwardDistances, backwardDistances;
vector<ll> memoForward, memoBackward;

ll computeForwardTime(ll idx, ll stepSize) {
    if (idx < 0) return 0;
    if (memoForward[idx] != -1) return memoForward[idx];
    return memoForward[idx] = 2LL * forwardDistances[idx] + computeForwardTime(idx - stepSize, stepSize);
}

ll computeBackwardTime(ll idx, ll stepSize) {
    if (idx < 0) return 0;
    if (memoBackward[idx] != -1) return memoBackward[idx];
    return memoBackward[idx] = 2LL * backwardDistances[idx] + computeBackwardTime(idx - stepSize, stepSize);
}

ll delivery(int numCheckpoints, int stepSize, int trackLength, int* checkpoints) {
    forwardDistances.clear();
    backwardDistances.clear();

    for (int i = 0; i < numCheckpoints; i++) {
        ll pos = checkpoints[i];
        if (pos == 0 || pos == trackLength) continue;
        if (2 * pos > trackLength)
            backwardDistances.push_back(trackLength - pos);
        else
            forwardDistances.push_back(pos);
    }

    sort(forwardDistances.begin(), forwardDistances.end());
    sort(backwardDistances.begin(), backwardDistances.end());

    memoForward.assign(forwardDistances.size(), -1);
    memoBackward.assign(backwardDistances.size(), -1);

    ll fCount = forwardDistances.size();
    ll bCount = backwardDistances.size();

    ll result = computeForwardTime(fCount - 1, stepSize) + computeBackwardTime(bCount - 1, stepSize);

    for (ll i = 0; i <= stepSize; ++i) {
        ll skipF = fCount - 1 - i;
        ll skipB = bCount - 1 - (stepSize - i);
        ll timeF = computeForwardTime(skipF, stepSize);
        ll timeB = computeBackwardTime(skipB, stepSize);
        result = min(result, timeF + timeB + trackLength);
    }

    return result;
}

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