Submission #147171

#	Time	Username	Problem	Language	Result	Execution time	Memory
147171		pit4h	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	655 ms	293908 KiB

boxes

#include<bits/stdc++.h>
#include "boxes.h"
#define ll long long
using namespace std;
ll delivery(int n, int k, int l, int pos[]) {
	vector<ll> pref(n), suf(n);
	for(int i=0; i<n; ++i) {
		if(i<k) {
			pref[i]=2*pos[i];
		}
		else {
			pref[i]=pref[i-k]+2*pos[i];
		}
	}
	for(int i=n-1; i>=0; --i) {
		if(i+k>=n) {
			suf[i]=2*(l-pos[i]);
		}
		else {
			suf[i]=suf[i+k]+2*(l-pos[i]);
		}
	}
	ll ans=min(pref[n-1], suf[0]);
	for(int i=0; i<n-1; ++i) {
		ans=min(ans, pref[i]+suf[i+1]);
	}
	ans=min(ans, pref[n-1-k]+l);
	ans=min(ans, suf[k]+l);
	for(int i=0; i<n-1-k; ++i) {
		ans=min(ans, pref[i]+suf[i+k+1]+l);
	}
	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