| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 538630 | chaoyue | 선물상자 (IOI15_boxes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}