Submission #789929

#	Time	Username	Problem	Language	Result	Execution time	Memory
789929		Sohsoh84	Wiring (IOI17_wiring)	C++17	17 / 100	1082 ms	9816 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll MAXN = 1e6 + 10;
const ll INF = 1e15 + 10;

ll dp[MAXN], ps[MAXN], len[MAXN];

ll min_total_length(vector<int> r, vector<int> b) {
	vector<pll> vec;
	vec.push_back({-1, -1});
	for (int i = 0; i < int(r.size()); i++) vec.push_back({r[i], 0});
	for (int i = 0; i < int(b.size()); i++) vec.push_back({b[i], 1});

	sort(all(vec));
	dp[0] = 0;
	int lst[2] = {0, 0};

	int n = int(vec.size()) - 1;
	for (int i = 1; i <= n; i++) {
		auto [x, t] = vec[i];
		lst[t] = i;
	
		ps[i] = ps[i - 1] + x;
		len[i] = (t == vec[i - 1].Y ? len[i - 1] + 1 : 1);

		int ind = lst[t ^ 1];
		int y = vec[ind].X;
		if (ind == 0) {
			dp[i] = INF;
			continue;
		}
	
		dp[i] = dp[i - 1] + x - y;
		if (len[i] > len[ind]) continue;
	
		ll s1 = ps[i] - ps[ind], s2 = ps[ind] - (ps[ind - len[i]]), f = 0;
		dp[i] = min(dp[i], dp[ind - len[i]] + s1 - s2);

		for (int j = ind - len[i]; j > 0 && vec[j].Y != t; j--) {
			f += vec[ind + 1].X - vec[j].X;
			dp[i] = min(dp[i], dp[j - 1] + s1 - s2 + f);
		}
	}

	return dp[n];
}

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