# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1197416 | pensive | Boxes with souvenirs (IOI15_boxes) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(a,i,n) for (ll i=a;i<n;i++)
const int mx = 1e7;
ll pre[mx+1], suf[mx+1];
ll delivery(ll N, ll K, ll L, ll positions[]) {
REP(0, i, N) {
pre[i] = min(pre[i] + 2*positions[i], L);
if (i>=K) {
pre[i] += pre[i-K];
}
}
ll ans = 1e11;
for (int i=N-1;i>=0;i--) {
suf[i] = min(suf[i] + 2*(L-positions[i]), L);
if (i <= N-K-1) {
suf[i] += suf[i+K];
}
ans = min(ans, ((i==0) ? 0 : pre[i-1])+suf[i]);
}
return ans;
}