Submission #1187665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187665		simona1230	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	2096 ms	27720 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;

long long n,k,l;
const long long maxn=1e7+5;
long long a[maxn];
long long p[maxn];
long long s[maxn];

long long delivery(int N, int K, int L, int P[])
{
    long long id=0;
    for(long long i=0;i<N;i++)
        if(P[i]==0)id=i+1,N--;
    n=N;
    k=K;
    l=L;
    for(long long i=0;i<n;i++)
        a[i]=P[id+i];

    for(long long i=0;i<n;i++)
    {
        p[i]=a[i]*2;
        if(i-k>=0)p[i]+=p[i-k];
    }

    for(long long i=n-1;i>=0;i--)
    {
        s[i]=(l-a[i])*2;
        if(i+k<=n-1)s[i]+=s[i+k];
    }

    long long ans=1e18;
    for(long long i=0;i<n;i++)
    {
        for(long long j=i+1;j<=n-1;j++)
        {
            long long lf=n-(i-0+1)-(n-1-j+1);
            long long lap=lf/k;
            if(lf%k)lap++;
            ans=min(ans,lap*l+p[i]+s[j]);
        }

        long long lf1=n-(i-0+1);
        long long lf2=n-(n-1-i+1);
        long long lap1=lf1/k;
        if(lf1%k)lap1++;
        long long lap2=lf2/k;
        if(lf2%k)lap2++;

        ans=min(ans,p[i]+lap1*l);
        ans=min(ans,s[i]+lap2*l);
    }

    long long lap=n/k;
    if(n%k)lap++;
    ans=min(ans,lap*l);

    return ans;
}

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