Submission #1185809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185809		Warinchai	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	344 ms	196380 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
long long l[10000005];
long long r[10000005];
long long delivery(int N, int K, int L, int p[]) {
    //cerr<<"work\n";
    for(int i=0;i<=N+1;i++)l[i]=r[i]=0;
    for(int i=1;i<=N;i++){
        int prv=max(0,i-K);
        l[i]=l[prv]+p[i-1]*2;
        //cerr<<l[i]<<" ";
    }
    //cerr<<"\n";
    for(int i=N;i>=1;i--){
        int prv=min(N+1,i+K);
        r[i]=r[prv]+(L-p[i-1])*2;
        //cerr<<r[i]<<" ";
    }
    //cerr<<"\n";
    //cerr<<"\n";
    long long ans=LLONG_MAX;
    for(int i=0;i<=N;i++){
        ans=min(ans,l[i]+r[i+1]);
        ///cerr<<i<<" "<<l[i]<<" "<<r[i+1]<<"\n";
    }
    for(int i=0;i+K<=N;i++){
        //cerr<<i<<" "<<l[i]+L+r[i+K+1]<<"\n";
        ans=min(ans,l[i]+L+r[i+K+1]);
    }
    //cerr<<"work\n";
    return ans;
}

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