Submission #33917

#	Time	Username	Problem	Language	Result	Execution time	Memory
33917		imeimi2000	Wiring (IOI17_wiring)	C++14	100 / 100	53 ms	10144 KiB

wiring

#include "wiring.h"
#include <algorithm>

using namespace std;
typedef long long llong;

const int R = 0, B = 1;
int n, m;
struct point {
	int x, k;
	bool operator<(const point &p) const {
		return x < p.x;
	}
};

point ps[200001];
int cnt[200001];
llong sum[200001];
llong dp[200001];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	n = r.size();
	m = b.size();
	int i = 0, j = 0, p = 0;
	while (i < n && j < m) {
		if (r[i] < b[j]) ps[++p] = { r[i++], R };
		else ps[++p] = { b[j++], B };
	}
	while (i < n) ps[++p] = { r[i++], R };
	while (j < m) ps[++p] = { b[j++], B };
	llong ret = 0ll;
	llong rd = -1e18, bd = -1e18;
	r.push_back(2e9);
	b.push_back(2e9);
	for (i = 0; i <= n + m; ++i) cnt[i] = -1;
	int ct = n;
	cnt[ct] = 0;
	for (p = 1, i = j = 0; p <= n + m; ++p) {
		int x = ps[p].x, k = ps[p].k;
		ct += (k + k - 1);
		
		sum[p] = sum[p - 1] + (k == R ? -x : x);
		if (k == B) {
			while (i < n && r[i] <= x) ++i;
			dp[p] = dp[p - 1] + min(x - rd, (llong)r[i] - x);
		}
		else {
			while (j < m && b[j] <= x) ++j;
			dp[p] = dp[p - 1] + min(x - bd, (llong)b[j] - x);
		}

		if (cnt[ct] != -1) {
			dp[p] = min(dp[p], dp[cnt[ct]] + abs(sum[p] - sum[cnt[ct]]));
		}

		if (k == R) rd = x;
		else bd = x;
		cnt[ct] = p;
	}
	return dp[n + m];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:30:8: warning: unused variable 'ret' [-Wunused-variable]
  llong ret = 0ll;
        ^

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