Submission #1184684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184684		vivkostov	Boxes with souvenirs (IOI15_boxes)	C++20	10 / 100	0 ms	328 KiB

boxes

//#pragma once
//#include "grader.cpp"
#include "boxes.h"
#include "bits/stdc++.h"
using namespace std;
long long int lef,rig,n,k,l,a[1000005],used[1000005],otg,ost,last=1e17,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
            {
                ma2=a[i];
                break;
            }
        }
    }
}
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])*2;
            break;
        }
    }
}
void get_from_right()
{
    int num=0;
    for(int i=n-1;i>=0;i--)
    {
        if(!used[i])num++;
        if(num==k)
        {
            if(i!=0)last=min(last,l+(a[i-1])*2);
            else last=l;
            break;
        }
    }
}
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;
    //PREC
    fix_l();
    fix_r();
    get_info();
    get_from_left();
    get_from_right();
    if(!ma2)otg=otg+min(ma1*2,last);
    else otg=otg+min(ma1*2+(l-ma2)*2,last);
    return otg;
}

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