Submission #239457

#	Time	Username	Problem	Language	Result	Execution time	Memory
239457		Jatana	Wiring (IOI17_wiring)	C++17	17 / 100	1090 ms	9064 KiB

wiring

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

#define le(v) ((int)v.size())

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

ll min_total_length(vector<int> r, vector<int> b) {
	vector<int> pos[2];
	pos[0] = r;
	pos[1] = b;
	vector<pii> v;
	for (int x : r) {
		v.emplace_back(x, 0);
	}
	for (int x : b) {
		v.emplace_back(x, 1);
	}
	sort(v.begin(), v.end());
	vector<ll> dp(le(v), 1e18);
	map<int, int> mem;
	mem[0] = -1;
	int pr = 0;
	for (int i = 0; i < le(v); i++) {
		if (v[i].y == 1) pr++;
		else pr--;
		int op = 1 - v[i].y;
		int ind = lower_bound(pos[op].begin(), pos[op].end(), v[i].x) - pos[op].begin();
		ll close = 1e18;
		for (int d : {ind, ind - 1}) {
			if (0 <= d && d < le(pos[op])) {
				close = min(close, (ll)abs(pos[op][d] - v[i].x));
			}
		}
		dp[i] = (i == 0 ? 0 : dp[i - 1]) + close;
		if (mem.count(pr)) {
			ll offset = 0;
			int l = mem[pr] + 1;
			for (int j = l; j <= i; j++) {
				if (v[j].y == v[i].y) {
					offset += v[j].x;
				} else offset -= v[j].x;
			}
			dp[i] = min(dp[i], offset + ((l - 1 >= 0) ? dp[l - 1] : 0));
		}
		mem[pr] = i;
	}
	return dp.back();
}

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