| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 101886 | pedro_sponchiado | 선물상자 (IOI15_boxes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000010;
const long long int INF=112345678912345678;
long long int resp=INF;
vector<long long int> dist[2];
long long int mini[maxn][2];
long long int aux[maxn][2];
long long int x[maxn];
long long delivery(int n, int s, long long int l, long long int pos[maxn]) {
scanf("%d %d %d", &n, &s, &l);
for(int i=0; i<n; i++){
scanf("%lld", &pos[i]);
if(pos[i]<l/2) dist[0].push_back(pos[i]);
if(pos[i]>l/2) dist[1].push_back(l-pos[i]);
}
//calcula mini
for(int k=0; k<=1; k++){
for(int i=0; i<dist[k].size(); i++){
aux[i%s][k]+=dist[k][i];
mini[i+1][k]=aux[i%s][k];
}
for(int i=dist[k].size(); i<=n; i++) mini[i+1][k]=INF;
}
//calcula x
for(int i=1; i<=n; i++){
x[i]=INF;
for(int k=0; k<=i; k++){
x[i]=min(x[i], mini[k][0]+mini[i-k][1]);
}
}
//calcula resp
for(int k=0; k<=n; k++){
if(n-k*s>=0) resp=min(resp, x[n-k*s]+k*l);
else resp=min(resp, k*l);
}
printf("%lld\n", 2*resp);
return 0;
}