| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1309258 | avohado | 선물상자 (IOI15_boxes) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
#define mp make_pair
#define all(x) x.begin(), x.end()
#define len(v) max(0, (int)v.size())
long long delivery(int N, int k, long long L, int p[]){
vector<int> l, r;
long long ans1=0, ans2=0;
for(int i=0; i<N; i++){
if(p[i]<(L+1)/2){
l.pb(p[i]);
}else{
r.pb(L-p[i]);
}
}
int i=0, j=0;
reverse(all(r));
while(i<len(l)){
int d=min(k, len(l)-i);
ans1+=l[i-1+d]*2;
i+=d;
}
i=0;
while(i<len(r)){
int d=min(k, len(r)-i);
ans1+=r[i-1+d]*2;
i+=d;
}
if(N<=k){
return min(ans1, L);
}
if(min(len(l), len(r))==0){
return ans1;
}
ans2=ans1;
i=max(0, len(l)-k);
ans1-=l[len(l)-1]*2;
if(len(l)%k!=0&&len(l)>k){
ans1-=(l[len(l)/k*k-1]*2);
}
if((i-1)%k!=0&&i!=0){
ans1+=(l[i-1]*2);
}
j=len(r)-1;
if(len(l)<k){
j-=k-len(l);
ans1-=r[len(r)-1]*2;
if(j%k!=0){
ans1+=r[j-1]*2;
}
}
while(i<len(l)&&j>=0){
ans2=min(ans1+L, ans2);
ans1+=l[i]*2;
ans1-=r[j]*2;
if((i-1)%k!=0&&i!=0){
ans1-=l[i-1]*2;
}
if((j-1)%k!=0&&j!=0){
ans2+=r[j-1];
}
i++;j--;
}
return min(ans1+L, ans2);
}