| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1343938 | ozner77 | Boxes with souvenirs (IOI15_boxes) | C11 | 0 ms | 0 KiB |
#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long delivery(int N, int K, int L, int p[]) {
vector<ll> V;
vector<ll> V_original;
for(int i=0;i<N;i++){
V_original.push_back(p[i]);
V.push_back(p[i]);
}
sort(V_original.begin(),V_original.end());
sort(V.begin(),V.end());
vector<ll> dpl(N,0);
vector<ll> dpr(N,0);
for(int i=0;i<N;i++){
if(i<K){
dpl[i]=2*V[i];
}else{
dpl[i]=dpl[i-K]+2*V[i];
}
}
V.clear();
for(int i=0;i<N;i++){
V.push_back(L-p[i]);
}
sort(V.begin(),V.end());
for(int i=0;i<N;i++){
if(i<K){
dpr[i]=2*V[i];
}else{
dpr[i]=dpr[i-K]+2*V[i];
}
}
ll ans=min(dpl[N-1],dpr[N-1]);
for(int i = 0; i < N; i++){
ll left=dpl[i];
ll right=0;
if(i+1<N){
right=dpr[N-2-i];
}
ll mx=V_original[i];
if(i+1< N){
mx=max(mx,(ll)(L-V_original[i+1]));
}
ans = min(ans, left + right - mx);
}
return ans;
}
