| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 668852 | Astrayt | 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>
using namespace std;
#define pb push_back
#define ll long long
#define int long long
#define pii pair<int,int>
#define All(x) x.begin(), x.end()
ll delivery(int N, int K, int L, int pos[]){
ll ans = 0;
vector<int> lp, rp;
for(int i = 0; i < N; ++i){
if(pos[i] != 0 && pos[i] <= L / 2) lp.pb(pos[i]);
else if(pos[i] > L / 2) rp.pb(pos[i]);
}
reverse(All(rp));
int cur = lp.size() + rp.size();
for(int i = cur; i > 0; ){
int k = min(K, i);
ll ml = 0, mr = 0;
for(; k; k--){
int l, r;
l = (lp.size() ? lp.back() : -1), r = (rp.size() ? rp.back() : L + 1);
if(ml == 0 && mr == 0){
if(l > (L - r)) ml = l, lp.pop_back();
else mr = (L - r), rp.pop_back();
}else if(ml && l >= (L - r)) lp.pop_back();
else if(mr && (L - r) >= l) rp.pop_back();
else{
if (ml && 2 * (ml + L - r) < L){
while(k && lp.size()) lp.pop_back(), k--, i--;
break;
}
else if(ml && r != L + 1){
mr = L - r;
rp.pop_back();
}else if(mr && 2 * (mr + l) < L){
while(k && rp.size()) rp.pop_back(), k--, i--;
break;
}
else if(mr && l != -1){
ml = l;
lp.pop_back();
}
}
i--;
}
ans += min(2ll * (ml + mr), 1ll * L);
}
return ans;
}