Submission #1267973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267973		WH8	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	349 ms	196104 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll delivery(int n, int k, int l, int p[]) {
    vector<ll> pfx(n+2, 0), sfx(n+2, 0);
    for(int i=1;i<=n;i++){
		pfx[i]=(i-k > 0 ? pfx[i-k] : 0)+p[i-1]*2;
	}
	for(int i=n;i>0;i--){
		sfx[i]=(i+k <= n? sfx[i+k] : 0)+(l-p[i-1])*2;
	}
	//~ for(int i=0;i<=n+1;i++){
		//~ cout<<pfx[i]<<" "<<sfx[i]<<endl;
	//~ }
	ll ans=LLONG_MAX;
	for(int i=0;i<=n;i++){
		ll no=pfx[i]+sfx[i+1];
		ll take=LLONG_MAX;
		if(i + k + 1 <= n+1){
			take=pfx[i]+sfx[i+k+1]+l;
		}
		ans=min({ans,no,take});
	} 
	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