Submission #1025742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025742		DorostWef	Wiring (IOI17_wiring)	C++17	100 / 100	76 ms	6512 KiB

wiring

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

using namespace std;
const int N = 200013;
long long dp[N];
long long ps[N];
vector <int> v;
bool c[N];

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector <int> blocks;
	int n = (int)r.size() + (int)b.size();
	v.push_back(-1);
	for (int x : r)
		v.push_back(x);
	for (int x : b)
		v.push_back(x);
	sort (v.begin(), v.end());
	for (int i = 1; i <= n; i++) {
		if ((*lower_bound (r.begin(), r.end(), v[i])) == v[i])
			c[i] = 0;
		else
			c[i] = 1;
		if (i == 0)
			ps[i] = v[i];
		else
			ps[i] = ps[i - 1] + v[i];
	}
	int cnt = 0;
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		if (i == 1 || c[i] != c[i - 1]) {
			blocks.push_back(cnt);
			cnt = 0;
		}
		cnt++;
		int near = INT_MAX;
		if (c[i] == 0) {
			int in = lower_bound (b.begin(), b.end(), v[i]) - b.begin();
			if (in != (int)b.size())
				near = abs (v[i] - b[in]);
			in--;
			if (in != -1) 
				near = min (near, abs (v[i] - b[in]));
		} else {
			int in = lower_bound (r.begin(), r.end(), v[i]) - r.begin();
			if (in != (int)r.size())
				near = abs (v[i] - r[in]);
			in--;
			if (in != -1) 
				near = min (near, abs (v[i] - r[in]));
		}
		dp[i] = dp[i - 1] + near;
		if (cnt <= blocks.back()) {
			long long ps1, ps2;
			ps1 = ps[i] - ps[i - cnt];
			ps2 = ps[i - cnt] - ps[i - cnt * 2];
			dp[i] = min (dp[i], dp[i - 2 * cnt] + ps1 - ps2);
		}
	}
	return dp[n];
}

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