Submission #434387

#	Time	Username	Problem	Language	Result	Execution time	Memory
434387		bipartite_matching	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	663 ms	284412 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);

	costl[0] = 2 * dist[0];

	for (int i = 1; i < n; i++) {
		costl[i] = i >= k ? (ll)(costl[i - k] + p[i] + dist[i]) : (ll)(p[i] + dist[i]);
	}

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

	for (int i = n - 2; i >= 0; i--) {
		costr[i] = i + k < n ? (ll)(costr[i + k] + l - p[i] + dist[i]) : (ll)(l - p[i] + dist[i]);
	}

	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];
	}

	/*forint(i, n) {
		cerr << costl[i] << " - " << costr[i] << endl;	
	}*/

	return ret;
}

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