Submission #540868

#	Time	Username	Problem	Language	Result	Execution time	Memory
540868		sliviu	Wiring (IOI17_wiring)	C++17	100 / 100	54 ms	10852 KiB

wiring

#include <bits/stdc++.h>    

using namespace std;
using ll = long long;

ll min_total_length(vector<int> r, vector<int> b) {
	int n = r.size(), m = b.size(), cr = 0, cb = 0;
	vector<pair<int, int>> a = {{0,0}};
	for (auto x : r)
		a.emplace_back(x, 0);
	for (auto x : b)
		a.emplace_back(x, 1);
	sort(a.begin() + 1, a.end());
	vector<ll> dp(n + m + 1, 1e18), sr(n + m + 1), sb(n + m + 1);
	vector<int> last(n + m + 1, -1);
	dp[0] = 0;
	last[m] = 0;
	for (int i = 1; i <= n + m; ++i) {
		auto [x, t] = a[i];
		++(t ? cb : cr);
		sr[i] = sr[i - 1], sb[i] = sb[i - 1];
		(t ? sb[i] : sr[i]) += x;
		if (t) {
			int j = lower_bound(r.begin(), r.end(), x) - r.begin();
			if (j != n)
				dp[i] = min(dp[i], dp[i - 1] + r[j] - x);
			if (j)
				dp[i] = min(dp[i], dp[i - 1] + x - r[j - 1]);
		}
		else {
			int j = lower_bound(b.begin(), b.end(), x) - b.begin();
			if (j != m)
				dp[i] = min(dp[i], dp[i - 1] + b[j] - x);
			if (j)
				dp[i] = min(dp[i], dp[i - 1] + x - b[j - 1]);
		}
		if (last[cr - cb + m] != -1) {
			int l = last[cr - cb + m];
			dp[i] = min(dp[i], dp[l] + abs((sr[i] - sr[l]) - (sb[i] - sb[l])));
		}
		last[cr - cb + m] = i;
	}
	return dp[n + m];
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45