Submission #1105567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105567		alexander707070	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	518 ms	333104 KiB

boxes

#include<bits/stdc++.h>
#include "boxes.h"
 
#define MAXN 10000007
using namespace std;
 
const long long inf=1e17;
 
int n,k,L;
int team[MAXN];
long long pref[MAXN],suff[MAXN],ans;
 
int cost(int l,int r){
    int a=min(team[l],L-team[r]);
    int c=team[r]-team[l];
 
    return min(2*(a+c),L);
}
 
long long delivery(int N, int K, int LL,int p[]) {
    n=N; k=K; L=LL;
 
    for(int i=1;i<=n;i++){
        team[i]=p[i-1];
    }
 
    pref[0]=0;
    for(int i=1;i<=n;i++){
        pref[i]=pref[max(i-k,0)]+cost(max(i-k+1,1),i);
    }
 
    suff[n+1]=0;
    for(int i=n;i>=1;i--){
        suff[i]=suff[min(i+k,n+1)]+cost(i,min(i+k-1,n));
    }
 
    ans=inf;
    for(int i=0;i<=n;i++){
        ans=min(ans,pref[i]+suff[i+1]);
    }
 
    if(n<=k)ans=min(ans,L+0LL);
 
    return ans;
}
 
/*int main(){
 
    cout<<delivery(3,2,8,{1,2,5})<<"\n";
 
	return 0;
}*/

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