Submission #1217980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217980		vidux	Boxes with souvenirs (IOI15_boxes)	C++17	20 / 100	0 ms	328 KiB

boxes

#include "boxes.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const ll LLINF = 1e18;

long long delivery(int n, int k, int l, int p[]) {
	vl a(n);
	for (int i = 0; i < n; i++) a[i] = p[i];
	a.push_back(l);
	vl tr(n+1);
	ll tot = 0;
	for (int i = n-1; i >= 0; i--) {
		tot += a[i+1]-a[i];
		tr[i] = tot + min(a[i], a[n]-a[i]);
		if ((n-i)%k==0) tot += min(a[i], a[n]-a[i]) + a[n]-a[i];
	}
	tot = 0;
	ll ans = tr[0];
	for (int i = 0; i < n; i++) {
		tot += a[i] - (i ? a[i-1] : 0);
		ll tl = tot + min(a[i], a[n]-a[i]);
		ans = min(ans, tl+tr[i+1]);
		if ((i+1)%k==0) tot += min(a[i], a[n]-a[i]) + a[i];
	}
	//cout << ans << endl;
	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