Submission #567082

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

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll delivery(int n, int k, int L, int p[]) {
	vector<ll>pref(n,0),suff(n,0);
	int cur = k;
	ll sum = 0;
	sort(p,p+n);
	int last = 0;
	for(int i=0;i<n;i++){
		if(!cur){
			pref[i]+=2*sum;
			cur = k;
		}
		cur--;
		pref[i]+=p[i] - last;
		sum+=p[i] - last;
		if(i)pref[i]+=pref[i-1];
		last = p[i];
	}
	last = L;
	sum = 0;
	cur = k;
	for(int i=n-1;i>=0;i--){
		if(!cur){
			suff[i]+=2*sum;
			cur = k;
		}
		cur--;
		suff[i]+=last - p[i];
		sum+=last - p[i];
		if(i!=n-1)suff[i]+=suff[i+1];
		last = p[i];
	}
	ll ans = 2e18;
	//for(int i=0;i<n;i++)cout<<pref[i]<<" ";
	//cout<<'\n';
	//for(int i=0;i<n;i++)cout<<suff[i]<<" ";
	//cout<<'\n';
	for(int i=0;i+1<n;i++){
		ll cost = pref[i] + suff[i+1] + min(p[i],L-p[i]) + min(p[i+1],L-p[i+1]);
		ans = min(ans,cost);
	}
	ans = min(pref[n-1] + min(p[n-1],L-p[n-1]),ans);
	ans = min(suff[0] + min(p[0],L-p[0]),ans);
    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