| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 538630 | chaoyue | Boxes with souvenirs (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;
#define ll long long
ll delivery(int a, int b, int c, int p[]){
ll N = a, K = b, L = c, split = L/2, idx=0, lsize=1, rsize=1, f0, ans=0;
vector<ll> left(N), right(N);
left[0] = 0, right[0] = 0;
while(idx < N && p[idx] <= split){
left[lsize] = p[idx] * 2;
if(lsize >= K) left[lsize] += left[lsize-K];
idx++, lsize++;
}
while(idx < N){
right[rsize] = (L - p[idx]) * 2;
if(rsize >= K) right[rsize] += right[rsize-K];
idx++, rsize++;
}
/*cout<<"left: ";
for(int i=0; i<lsize; i++){
cout<<left[i]<<" ";
}
cout<<"\nright: ";
for(int i=0; i<rsize; i++){
cout<<right[i]<<" ";
}
cout<<"\n";*/
//left is non-decreasing
//pre array will flip left & right arrays
vector<ll> lpre(lsize), rpre(rsize);
lpre[0] = 0, rpre[0] = 0;
for(ll i=1; i<lsize; i++){
lpre[i] = lpre[i-1] + left[lsize-i] - left[lsize-i-1];
}
for(ll i=1; i<rsize; i++){
rpre[i] = rpre[i-1] + right[rsize-i] - right[rsize-i-i];
}
/*cout<<"lpre: ";
for(int i=0; i<lsize; i++){
cout<<lpre[i]<<" ";
}
cout<<"\nrpre: ";
for(int i=0; i<rsize; i++){
cout<<rpre[i]<<" ";
}
cout<<"\n";*/
f0 = left[lsize-1] + right[rsize-1]; //initial answer if 0 loops
vector<ll> opt(K); //calculates optimal value of lpre assuming rpre takes i souvenirs
for(ll i=0; i<K; i++){
opt[i] = lpre[lsize-1] - ceil((lsize-1 + i) / K) * L; //if take everything
if(i) opt[i] = max(opt[i], -L); //if take nothing
else opt[i] = max(opt[i], 0);
for(ll j=1; j*K-i<lsize; j++){ //takes care of middle part
opt[i] = max(opt[i], lpre[j * K - i] - j * L);
}
}
/*cout<<"opt: ";
for(int i=0; i<K; i++){
cout<<opt[i]<<" ";
}
cout<<"\n";*/
for(int i=1; i<rsize; i++){
ans = max(ans, rpre[i] + opt[i%K] - i/K * L);
}
ans = min(f0, f0-ans);
//cout<<f0<<"\n";
cout<<ans;
return ans;
}