| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 668811 | 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 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;
bool in_mid = 0;
for(int i = 0; i < N; ++i){
if(pos[i] == L / 2 && L % 2 == 0) in_mid = 1;
else 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));
if(in_mid){
int k = min((int)lp.size() + (int)rp.size(), K - 1);
for(; k; k--){
int l = (lp.size() ? lp.back() : -1), r = (rp.size() ? rp.back() : L + 1);
if(l < (L - r)) rp.pop_back();
else if(l > (L - r)) lp.pop_back();
else{
lp.pop_back(), rp.pop_back();
int nl = (lp.size() ? lp.back() : -1), nr = (rp.size() ? rp.back() : L + 1);
if(nl > (L - nr)) lp.pb(l);
else rp.pb(r);
}
}
ans += 1ll * L;
}
int cur = lp.size() + rp.size();
for(int i = cur; i > 0; i -= K){
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(l < (L - r)) rp.pop_back(), mr = max(mr, 1ll * (L - r));
else if(l > (L - r)) lp.pop_back(), ml = max(ml, 1ll * l);
else {
if(mr) rp.pop_back(), mr = max(mr, 1ll * (L - r));
else lp.pop_back(), ml = max(ml, 1ll * l);
}
}
ans += min(2ll * (ml + mr), 1ll * L);
}
return ans;
}
int main(){
int n, k, l; cin >> n >> k >> l;
int pos[n];
for(auto &x:pos) cin >> x;
cout << delivery(n, k, l, pos) << '\n';
return 0;
}