| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 82059 | wzy | Boxes with souvenirs (IOI15_boxes) | C++11 | 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;
#define F first
#define S second
long long dpL[10000001] , dpR[10000001];
long long delivery(int N, int K, int L, int p[]) {
#define int long long
int ans = (int) 1e18;
int k = K;
int n = N;
int l = L;
for(int i = 0 ; i < N ;i ++){
dpL[i] = 2*p[i];
if(i >= K) dpL[i] = dpL[i-k] + 2*p[i]; // pick the last block and then solve for [0 , i-k]
}
for(int j = N - 1 ; j >= 0 ; j--){
int u = j + K ;
dpR[j] = 2*(L - p[j]);
if(u <= n - 1) dpR[j] = dpR[u] + 2*(L - p[j]);
}
#define pii pair<long long, long long>
deque<pii> dq;
int left = 1;
for(int i = 0 ; i < N - 1; i ++){
while(dq.size() && dq.front().second <= i) dq.pop_front();
left = max(left, i + 1);
while(left < N && k >= (left - i - 1)){
while(dq.size() && dq.back().first >= dpR[left]) dq.pop_back();
dq.push_back(pii(dpR[left] , left));
left++;
}
ans = min(ans , dpL[i] + dpR[i+1]);
ans = min(ans , dpL[i] + dq.front().F + L);
}
for(int i = 0 ; i < N ; i ++){
int X = n - i - 1;
if(X <= k){
ans = min(ans , dpL[i] + L);
}
int Y = i;
if(Y <= k) ans = min(ans , dpR[i] + L);
}
ans = min(ans , dpL[N - 1]);
ans = min(ans , dpR[0]);
if(K == N){
ans = min(ans ,L);
}
return ans;
}