Submission #1216077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216077		JooDdae	Wiring (IOI17_wiring)	C++20	100 / 100	45 ms	8376 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long min_total_length(vector<int> r, vector<int> b) {
	vector<array<int, 2>> v;
	for(auto x : r) v.push_back({x, -1});
	for(auto x : b) v.push_back({x, 1});
	sort(v.begin(), v.end());

	int N = v.size();
	vector<ll> dp(N+1, (ll)1e18), s(N+1, 0);
	vector<int> lev(N+N+1, -1), R(3, 0), L(3, -1);

	dp[0] = 0, lev[N] = 0;

	for(int i=1, u=N;i<=N;i++) {
		auto [x, y] = v[i-1];
		u += y, s[i] = s[i-1] + x*y;
		while(R[1-y] < N && (R[1-y] < i || v[R[1-y]][1] == y)) R[1-y]++;
		if(R[1-y] < N) dp[i] = dp[i-1] + v[R[1-y]][0]-x;
		if(L[1-y] != -1) dp[i] = min(dp[i], dp[i-1] + x-L[1-y]);
		if(lev[u] != -1) dp[i] = min(dp[i], dp[lev[u]] + abs(s[i]-s[lev[u]]));
		lev[u] = i, L[y+1] = x;
	}

	return dp[N];
}

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