Submission #1191662

#TimeUsernameProblemLanguageResultExecution timeMemory
1191662gelov선물상자 (IOI15_boxes)C++20
100 / 100
787 ms232136 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...