# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
479866 | ntabc05101 | Boxes with souvenirs (IOI15_boxes) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
#define taskname "CAKES"
const int mxN = 1000000;
long long delivery(int n, int k, int l, vector<int> P) {
vector<int> p;
for (auto &x: P) {
if (x != 0) {
p.push_back(x);
}
}
n = p.size();
//return 0;
vector<long long> dp_cw(n), dp_ccw(n);
for (int i = 0; i < n; i++) {
if (i < k) {
dp_cw[i] = min(l, 2 * p[i]);
}
else {
dp_cw[i] = min(l, 2 * p[i]) + dp_cw[i - k];
}
}
for (int i = n - 1; i >= 0; i--) {
if (i >= n - k) {
dp_ccw[i] = min(l, 2 * (l - p[i]));
}
else {
dp_ccw[i] = min(l, 2 * (l - p[i])) + dp_ccw[i + k];
}
}
long long res = min(dp_cw[n - 1], dp_ccw[0]);
for (int i = 1; i < n; i++) {
res = min(res, dp_cw[i - 1] + dp_ccw[i]);
}
return res;
}