# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
802289 | Liudas | 선물상자 (IOI15_boxes) | C++17 | 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 <bits/stdc++.h
#include "boxes.h
using namespace std;
vector<long long> get_cost(int N, int K, int L, int pos[]){
vector<long long> arr(N, 0);
for(int i = 0; i < N; i ++){
arr[i] += pos[i];
if(i >= K)arr[i] += arr[i-K] + pos[i-K];
}
return arr;
}
long long delivery(int N, int K, int L, int pos[]){
vector<long long> l, r;
l = get_cost(N, K, L, pos);
reverse(pos, pos + N);
for(int i = 0; i < N; i ++){
pos[i] = (pos[i] ? L - pos[i] : pos[i]);
}
r = get_cost(N, K, L, pos);
long long ans = min({l.back()+pos[0], l.back()+L-pos[0], r.back()+pos[N-1], r.back()-pos[N-1]+L});
reverse(pos, pos + N);
reverse(r.begin(), r.end());
for(int i = 0; i < N; i ++){
pos[i] = (pos[i] ? L - pos[i] : pos[i]);
}
for(int i = 0; i < N - 1; i ++){
cout << ans << endl;
ans = min(ans, l[i]+r[i+1]+min(L-pos[i],pos[i])+min(L-pos[i+1], pos[i+1]));
}
return ans;
}