Submission #434248

#	Time	Username	Problem	Language	Result	Execution time	Memory
434248		bipartite_matching	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	1 ms	296 KiB

boxes

#include <bits/stdc++.h>
#define forint(i, N) for (int i = 0; i < (N); i++)

using namespace std;

typedef long long ll;

ll delivery(int n, int k, int l, int p[]) {
	vector<int> dist(n);

	for (int i = 0; i < n; i++) {
		dist[i] = min(p[i], l - p[i]);
	}

	vector<ll> costl(n);
	vector<ll> costr(n);

	int a = 1;
	costl[0] = 2 * dist[0];

	for (int i = 1; i < n; i++) {
		costl[i] = (ll)(costl[i - 1] + 2 * (p[i] - p[i - 1]));
		if (a == 0) costl[i] += (ll)dist[i];
		if (a == k) a = 0;
	}

	a = 1;
	costr[n - 1] = 2 * dist[n - 1];

	for (int i = n - 2; i >= 0; i--) {
		costr[i] = (ll)(costr[i + 1] + 2 * (p[i + 1] - p[i]));
		if (a == 0) costr[i] += (ll)dist[i];
		if (a == k) a = 0;
	}

	ll ret = min(costl[n - 1], costr[0]);
	forint(i, n - 1) {
		if (costl[i] + costr[i + 1] < ret) ret = costl[i] + costr[i + 1];
	}
	return ret;
}

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