Submission #375967

#	Time	Username	Problem	Language	Result	Execution time	Memory
375967		ponytail	Boxes with souvenirs (IOI15_boxes)	C++17	20 / 100	1 ms	364 KiB

boxes

#include "boxes.h"
#include "bits/stdc++.h"
#define ll long long
using namespace std;
ll delivery(int N,int K,int L,int positions[]){
    if(K==1){
        ll ans=0;
        for(int i=0;i<N;i++){
            ans+=min(positions[i],L-positions[i])*2;
        }
        return ans;
    }
    if(K==N){
        ll ans=1e18;
        ans=min(ans,L*1LL);
        ans=min(ans,(L-positions[0])*2LL);
        ans=min(ans,positions[N-1]*2LL);
        for(int i=0;i<N-1;i++){
            ans=min(ans,positions[i]*2LL+(L-positions[i+1])*2LL); 
        }
        return ans;
    }
    ll pref[N], suf[N];
    for(int i=0;i<K;i++){
        pref[i]=positions[i];
    }
    for(int i=K;i<N;i++){
        pref[i]=pref[i-K]+positions[i];
    }
    for(int i=N-1;i>=N-K;i--){
        suf[i]=(L-positions[i]);
    }
    for(int i=N-K-1;i>=0;i--){
        suf[i]=suf[i+K]+(L-positions[i]);
    }
    ll ans=1e18;
    for(int i=0;i<N-1;i++){
        ans=min(ans,(pref[i]+suf[i+1])*2LL);
        ans=min(ans,pref[i]+L-positions[i]+suf[i+1]*2LL);
        ans=min(ans,pref[i]*2LL+suf[i+1]+positions[i+1]);
        ans=min(ans,pref[i]+L-positions[i]+suf[i+1]+positions[i+1]);
    }
    ans=min(ans,suf[0]+min(L-positions[0],positions[0]));
    ans=min(ans,pref[N-1]+min(L-positions[N-1],positions[N-1]));
    return ans;
}

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