Submission #1216959

#TimeUsernameProblemLanguageResultExecution timeMemory
1216959takoshanavaBoxes with souvenirs (IOI15_boxes)C++20
10 / 100
0 ms328 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; long long dist(int x, int L ){ return (x + L) % L; } long long delivery(int N, int K, int L, int pos[]) { sort(pos, pos+N, [&](int a, int b){ return dist(a, L) < dist(b, L); }); vector<int> p(pos, pos+N); vector<int> q = p; reverse(q.begin(), q.end()); vector<long long> l(N+1, 0), r(N+1, 0); for (int i = 1; i <= N; i++) { long long d = dist(p[i-1] - 0, L); if (i <= K) { l[i] = 2*d; } else { l[i] = l[i-K] + 2*d; } } for (int i = 1; i <= N; i++) { long long d = (L - q[i-1]) % L; if (i <= K) { r[i] = 2*d; } else { r[i] = r[i-K] + 2*d; } } long long ans = LLONG_MAX; for (int s = 0; s <= N; s++) { ans = min(ans, l[s] + r[N-s]); } int M = min(K, N); for (int t = 0; t + M <= N; t++) { long long cost1 = l[t]; long long cost2 = (long long)L; long long cost3 = r[N - (t+M)]; ans = min(ans, cost1 + cost2 + cost3); } 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...