Submission #1185808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185808		Warinchai	Boxes with souvenirs (IOI15_boxes)	C++20	10 / 100	0 ms	328 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";
    long long prv=0;
    long long go=0;
    for(int i=0;i<=N+1;i++)l[i]=r[i]=0;
    long long cnt=0;
    for(int i=1;i<=N;i++){
        if(p[i-1]==0){
            l[i]=l[i-1];
            continue;
        }
        cnt++;
        if(cnt%K==1){
            prv=l[i-1];
            go=0;
        }
        go=p[i-1];
        l[i]=prv+go*2;
        //cerr<<l[i]<<" ";
    }
    //cerr<<"\n";
    cnt=0;
    for(int i=N;i>=1;i--){
        if(p[i-1]==0){
            r[i]=r[i+1];
            continue;
        }
        cnt++;
        if(cnt%K==1){
            prv=r[i+1];
            go=0;
        }
        go=L-p[i-1];
        r[i]=prv+go*2;
        //cerr<<r[i]<<" ";
    }
    //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: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30