# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1184663 | vivkostov | 선물상자 (IOI15_boxes) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
#pragma once
#include "grader.cpp"
#include "boxes.h"
using namespace std;
long long int lef,rig,n,k,l,a[1000005],used[1000005],otg,ost,last=1e15,ma1,ma2;
void fix_l()
{
for(int i=k-1;i<n;i+=k)
{
if(a[i]>lef||ost-k<k)break;
ost-=k;
otg+=a[i]*2;
for(int j=i;j>=i-k+1;j--)used[j]=1;
}
}
void fix_r()
{
for(int i=n-k;i>=0;i-=k)
{
if(a[i]<rig||ost-k<k)break;
ost-=k;
otg+=(l-a[i]*2);
for(int j=i;j<=i+k-1;j++)used[j]=1;
}
}
void get_info()
{
for(int i=0;i<n;i++)
{
if(!used[i])
{
if(a[i]<=lef)ma1=a[i];
else if(!ma2)ma2=a[i];
}
}
}
void get_from_left()
{
int num=0;
for(int i=0;i<n;i++)
{
if(!used[i])num++;
if(num==k)last=l+(l-a[i+1]);
}
}
void get_from_right()
{
int num=0;
for(int i=n-1;i>=0;i--)
{
if(!used[i])num++;
if(num==k)last=min(last,l+(a[i-1]));
}
}
long long int delivery(int N, int K, int L, int P[])
{
n=N;
ost=N;
k=K;
l=L;
for(int i=0;i<n;i++)
{
a[i]=P[i];
}
lef=(l-1)/2;
rig=(l+1)/2;
sort(a,a+n);
//PREC
fix_l();
fix_r();
get_info();
otg=otg+min(ma1*2+(l-ma2)*2,last);
//cout<<otg<<endl;
return otg;
}