| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 668843 | Astrayt | 선물상자 (IOI15_boxes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
int in_mid = 0;
for(int i = 0; i < N; ++i){
if(pos[i] == L / 2 && L % 2 == 0) in_mid++;
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));
while(in_mid){
in_mid--;
int k = min((int)lp.size() + (int)rp.size() + in_mid, K - 1);
for(; k; k--){
int l = (lp.size() ? lp.back() : -1), r = (rp.size() ? rp.back() : L + 1);
if(in_mid) in_mid--;
else 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(mr && r != L + 1) rp.pop_back(), mr = max(mr, 1ll * (L - r));
else if(ml && l != -1) lp.pop_back(), ml = max(ml, 1ll * l);
else {
if(ml && l == -1 && 2ll * ml + 2ll * (L - r) < L) break;
if(mr && r == L + 1 && 2ll * mr + 2ll * l < L) break;
if(r == L + 1) lp.pop_back(), ml = max(ml, 1ll * l);
else rp.pop_back(), mr = max(mr, 1ll * (L - r));
}
}
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;
}