Submission #239456

#	Time	Username	Problem	Language	Result	Execution time	Memory
239456		Jatana	Wiring (IOI17_wiring)	C++17	17 / 100	1098 ms	7912 KiB

wiring

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

#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);
	for (int i = 0; i < le(v); i++) {
		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;
		deque<int> deq{i};
		ll offset = 0;
		for (int j = i - 1; j >= 0; j--) {
			if (v[deq.back()].y != v[j].y) {
				offset += v[deq.back()].x - v[j].x;
				deq.pop_back();
			} else deq.push_back(j);
			if (deq.empty()) {
				dp[i] = min(dp[i], offset + ((j - 1 >= 0) ? dp[j - 1] : 0));
				break;
			}
		}
	}
	return dp.back();
}

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