Submission #594377

#	Time	Username	Problem	Language	Result	Execution time	Memory
594377		KrisjanisP	Boxes with souvenirs (IOI15_boxes)	C++14	50 / 100	2045 ms	29496 KiB

boxes

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

long long delivery(int N, int K, int L, int p[]) {
    ll res = 1ll*((N+K-1)/K)*L;
    ll lmov[N],rmov[N];
    for(ll i=0;i<N;i++)
    {
        lmov[i] = p[i];
        ll left = K-1;
        for(ll j=i-1;j>=0;j--)
        {
            lmov[i]+=p[j+1]-p[j];
            if(left) left--;
            else
            {
                lmov[i]+=p[j]*2;
                left = K-1;
            }
        }
        lmov[i]+=p[0];
    }
    for(ll i=N-1;i>=0;i--)
    {
        rmov[i] = (L-p[i]);
        ll left = K-1;
        for(ll j=i+1;j<N;j++)
        {
            rmov[i]+=p[j]-p[j-1];
            if(left) left--;
            else
            {
                rmov[i]+=(L-p[j])*2;
                left = K-1;
            }
        }
        rmov[i]+=(L-p[N-1]);

    }
    //cout<<"lmov: "; for(ll i=0;i<N;i++) cout<<lmov[i]<<" "; cout<<"\n";
    //cout<<"rmov: "; for(ll i=0;i<N;i++) cout<<rmov[i]<<" "; cout<<"\n";
    res = min(res,lmov[N-1]);
    res = min(res,rmov[0]);
    for(ll l=0;l<N;l++)
    {
        for(ll r=l+1;r<N;r++)
        {
            ll left = r-l-1;
            res = min(res, lmov[l]+rmov[r]+1ll*((left+K-1)/K)*L);
        }
    }
    for(ll i=0;i<N;i++)
    {
        res = min(res, lmov[i]+1ll*((N-(i+1)+K-1)/K)*L);
        res = min(res, rmov[i]+1ll*((i+K-1)/K)*L);
    }
    return res;
}

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