# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
479865 | 2021-10-13T16:52:29 Z | ntabc05101 | Boxes with souvenirs (IOI15_boxes) | C++14 | 0 ms | 0 KB |
#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; }