Submission #227702

#	Time	Username	Problem	Language	Result	Execution time	Memory
227702		staniewzki	Wiring (IOI17_wiring)	C++17	100 / 100	68 ms	12520 KiB

wiring

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
using LL = long long;
using PII = pair<int, int>;

#include "wiring.h"

LL min_total_length(vector<int> r, vector<int> b) {
	vector<PII> p;
	for(int x : r) p.emplace_back(x, 1);
	for(int x : b) p.emplace_back(x, 2);
	sort(p.begin(), p.end());

	int n = size(p);
	vector<int> s(n);
	FOR(i, 1, n - 1)
		s[i] = (p[i].ND != p[i - 1].ND ? i : s[i - 1]);

	LL inf = 1e18;
	vector<LL> dp(n, inf), x(n), y(n, inf), sum(n);
	REP(i, n) sum[i] = (i != 0 ? sum[i - 1] : 0) + p[i].ST;

	auto get = [&](int l, int r) { 
		return sum[r] - (l != 0 ? sum[l - 1] : 0);
	};

	REP(i, n) {
		if(s[i] == 0) continue;
		int u = s[i] - 1, v = s[i];
		auto rel = [&](int l, int r) {
			return abs(get(l, r) - LL(r - l + 1) * p[v].ST);
		};

		if(v == i) {
			LL cur = inf;
			FOR(j, s[u], u) {
				cur = min(cur, (j == 0 ? 0 : dp[j - 1]) + rel(j, u));
				x[j] = cur;	
			}
			cur = inf;
			for(int j = v; j < n && s[j] == v; j++) {
				int t = u + v - j;
				cur += p[j].ST - p[u].ST;
				if(s[u] <= t) {
					cur = min(cur, rel(t, u) + rel(v, j) + (t == 0 ? 0 : dp[t - 1]));
				}
				y[j] = cur;
			}
		}

		if(s[i] - s[s[i] - 1] == 1)
			dp[i] = min(dp[u], (u == 0 ? 0 : dp[u - 1])) + rel(v, i) + LL(i - u) * (p[v].ST - p[u].ST);
		else {
			dp[i] = y[i];
			if(i - u <= u - s[u] + 1)
				dp[i] = min(dp[i], x[u - (i - v)] + rel(v, i));
		}
	}

	return dp[n - 1];
}

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