# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1185684 | vivkostov | Boxes with souvenirs (IOI15_boxes) | C++20 | 0 ms | 0 KiB |
#pragma once
#include "grader.cpp"
#include "boxes.h"
#include "bits/stdc++.h"
using namespace std;
long long int n,k,m,a[10000005],l,r,used[10000005],mi;
long long int go_from_left()
{
int num=0;
long long int otg=0;
for(int i=1;i<=n;i++)
{
if(a[i]!=0)num++;
if(num==k||i==n)
{
if(a[i]<=l)otg+=a[i]*2;
else if(a[i-num+1]<=l)otg+=m;
else otg+=(m-a[i-num+1])*2;
num=0;
}
}
return otg;
}
long long int go_from_right()
{
int num=0;
long long int otg=0;
for(int i=n;i>=1;i--)
{
num++;
if(num==k||i==1)
{
if(a[i]>=r)otg+=(m-a[i])*2;
else if(a[i+num-1]>=r)otg+=m;
else otg+=a[i+num-1]*2;
num=0;
}
}
return otg;
}
long long int go_from_mid()
{
int num=0;
long long int otg=0;
for(int i=1;i<=n;i++)
{
if(a[i]<=l&&a[i]!=0)num++;
if(num==k||a[i]>l||i==n)
{
if(a[i]>l)i--;
otg+=a[i]*2;
num=0;
if(a[i+1]>l)break;
}
}
for(int i=n;i>=1;i--)
{
if(a[i]>=r)num++;
if(num==k||a[i]<r||i==1)
{
if(a[i]<r)i++;
otg+=(m-a[i])*2;
num=0;
if(a[i-1]<r)break;
}
}
return otg;
}
long long int delivery(int N, int K, int L, int p[])
{
n=N;
k=K;
m=L;
for(int i=0;i<n;i++)
{
a[i+1]=p[i];
}
l=(m-1)/2;
r=(m+1)/2;
mi=min(go_from_left(),go_from_right());
mi=min(mi,go_from_mid());
cout<<mi<<endl;
return mi;
}