Submission #1241816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241816		Faggi	Boxes with souvenirs (IOI15_boxes)	C++20	50 / 100	46 ms	20004 KiB

boxes

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define fr first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;



long long delivery(int N, int K, int L, int p[])
{
    vector<ll>der,iz,agIz,agDer;
    ll sobIz=0, sobDer=0, ant;
    ll cost=0,i, sob=0;
    for(i=0; i<N; i++)
    {
        if(p[i]<(L+1)/2)
        {
            iz.pb(p[i]);
        }
        else
        {
            der.pb(p[i]);
        }
    }
    reverse(all(iz));
    while(sz(iz)&&iz.back()==0)
        iz.pop_back();
    agIz.resize(sz(iz),0);
    agDer.resize(sz(der),0);
    sort(all(iz));
    sort(all(der));
    for(i=0; i<sz(iz); i++)
    {
        if(sob==0)
        {
            agIz[i]=iz[i]*2ll;
            cost+=iz[i];
            sob=K-1;
        }
        else
        {
            cost+=iz[i]-iz[i-1];
            agIz[i]=(iz[i]-iz[i-1])*2ll;
            sob--;
        }
        if(sob==0)
        {
            cost+=iz[i];
        }
        else if(i+1==sz(iz))
        {
            cost+=iz[i];
        }
    }
    sobIz=sob;
    reverse(all(der));
    sob=0;
    for(i=0; i<sz(der); i++)
    {
        if(sob==0)
        {
            agDer[i]=(L-der[i])*2ll;
            cost+=(L-der[i]);
            sob=K-1;
        }
        else
        {
            agDer[i]=((L-der[i])-(L-der[i-1]))*2ll;
            cost+=abs((L-der[i])-(L-der[i-1]));
            sob--;
        }
        if(sob==0)
        {
            cost+=(L-der[i]);
        }
        else if(i+1==sz(der))
        {
            cost+=(L-der[i]);
        }
    }
    sobDer=sob;
    ll mi=cost,au=cost;
    if(sobIz>0)
    {
        cost-=iz.back();
        ant=iz.back();
        for(i=sz(der)-1; i>=0; i--)
        {
            cost-=agDer[i];
            cost+=abs(ant-der[i]);
            ant=der[i];
            sobIz--;
            if(sobIz==0||i-1<0)
            {
                cost+=(L-der[i]);
                break;
            }
        }
        mi=min(mi,cost);
    }
    cost=au;

    if(sobDer>0&&sz(iz))
    {
        cost-=(L-der.back());
        ant=der.back();
        for(i=sz(iz)-1; i>=0; i--)
        {
            cost-=agIz[i];
            cost+=abs(ant-iz[i]);
            ant=iz[i];
            sobDer--;
            if(sobDer==0||i-1<0)
            {
                cost+=iz[i];
                break;
            }
        }
        mi=min(mi,cost);
    }
    cost=0;
    sob=0;
    for(i=sz(der)-1; i>=0; i--)
    {
        if(sob==0)
        {
            cost+=(L-der[i])*2ll;
            sob=K-1;
        }
        else
        {
            sob--;
        }
    }
    sob=0;
    for(i=sz(iz)-1; i>=0; i--)
    {
        if(sob==0)
        {
            cost+=iz[i]*2ll;
            sob=K-1;
        }
        else
        {
            sob--;
        }
    }
    mi=min(cost,mi);



    //IZ
    cost=0, sob=0, ant=0;
    for(i=0; i<sz(iz); i++)
    {
        if(sob==0)
        {
            cost+=iz[i];
            sob=K-1;
        }
        else
        {
            cost+=abs(ant-iz[i]);
            sob--;
        }
        if(sob==0)
        {
            cost+=iz[i];
        }
        ant=iz[i];
    }
    if(sob>0&&sz(der))
    {
        ll ult=sz(der)-1;
        for(i=sz(der)-1; i>=0; i--)
        {
            sob--;
            ult=i;
            cost+=abs(der[i]-ant);
            if(sob==0||i-1==0)
            {
                cost+=(L-der[i]);
                break;
            }
            ant=der[i];
        }
        sob=0;
        ant=0;

        for(i=ult-1; i>=0; i--)
        {
            if(sob==0)
            {
                sob=K-1;
                cost+=(L-der[i])*2ll;
            }
            else
            {
                sob--;
            }
        }
        mi=min(cost,mi);
    }




    //DER
    cost=0, sob=0, ant=0;
    for(i=0; i<sz(der); i++)
    {
        if(sob==0)
        {
            cost+=(L-der[i]);
            sob=K-1;
        }
        else
        {
            cost+=abs(ant-der[i]);
            sob--;
        }
        if(sob==0)
        {
            cost+=(L-der[i]);
        }
        ant=der[i];
    }
    if(sob>0&&sz(iz))
    {
        ll ult=sz(iz)-1;
        for(i=sz(iz)-1; i>=0; i--)
        {
            sob--;
            ult=i;
            cost+=abs(iz[i]-ant);
            if(sob==0||i-1==0)
            {
                cost+=iz[i];
                break;
            }
            ant=iz[i];
        }
        sob=0;
        ant=0;

        for(i=ult-1; i>=0; i--)
        {
            if(sob==0)
            {
                sob=K-1;
                cost+=iz[i]*2ll;
            }
            else
            {
                sob--;
            }
        }
        mi=min(cost,mi);
    }



    return mi;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30