| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1359021 | c0det1ger | Boxes with souvenirs (IOI15_boxes) | C++20 | 0 ms | 0 KiB |
#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
long long delivery(int N, int K, int L, int p[]) {
sort(p, p + N);
vector<int> left, right;
for (int i = 0; i < N; i++){
if (p[i] > L / 2){
right.push_back(L - p[i]);
}
else{
left.push_back(p[i]);
}
}
right.push_back(0);
reverse(right.begin(), right.end());
vector<int> dp1(left.size()), dp2(right.size());
for (int i = 1; i < left.size(); i++){
if (i < K){
dp1[i] = left[i];
}
else{
dp1[i] = left[i] + dp1[i - K];
}
}
for (int i = 1; i < right.size(); i++){
if (i < K){
dp2[i] = right[i];
}
else{
dp2[i] = right[i] + dp2[i - K];
}
}
int mi = dp1.back() + dp2.back();
for (int i = 0; i < K; i++){
int a = dp1.size() - i - 1;
int b = dp2.size() - (K - i) - 1;
if (a >= 0 && b >= 0){
mi = min(mi, L + dp1[a] + dp2[b]);
}
}
return mi;
}