Submission #1007109

#TimeUsernameProblemLanguageResultExecution timeMemory
1007109The_SamuraiBoxes with souvenirs (IOI15_boxes)C++17
100 / 100
588 ms293968 KiB
#include "boxes.h" #include "bits/stdc++.h" using namespace std; using ll = long long; ll delivery(int n, int k, int L, int p[]) { auto dist = [&](int i, int j) -> int { return min(abs(i - j), L - abs(i - j)); }; sort(p, p + n); vector<ll> pref(n), suff(n + 1); for (int i = 0; i < n; i++) { pref[i] = p[i] + dist(0, p[i]); if (i >= k) pref[i] += pref[i - k]; // for (int j = i; j < min(n, i + k); j++) { // pref[j] = i > 0 ? pref[i - 1] : 0; // pref[j] += p[j] + dist(0, p[j]); // } } for (int i = n - 1; i >= 0; i--) { suff[i] = (L - p[i]) + dist(0, p[i]); if (i + k < n) suff[i] += suff[i + k]; // for (int j = i; j >= max(0, i - k + 1); j--) { // suff[j] = suff[i + 1]; // suff[j] += (L - p[j]) + dist(0, p[j]); // } } ll ans = min(pref[n - 1], suff[0]); for (int i = 1; i < n; i++) { ans = min(ans, pref[i - 1] + suff[i]); } return ans; }
#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...