Submission #800789

#	Time	Username	Problem	Language	Result	Execution time	Memory
800789		faruk	Wiring (IOI17_wiring)	C++17	100 / 100	48 ms	15808 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(), a.end()

using namespace std;

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

vector<ll> r, b;
vector<pii> arr;

ll dist_to_nearest(ll idx) {
	vector<ll> *my;
	if (arr[idx].second == 1)
		my = &b;
	else
		my = &r;
	
	auto pnt = lower_bound(my->begin(), my->end(), arr[idx].first);
	if (pnt == my->end())
		return abs(arr[idx].first - *prev(pnt));
	else if (pnt == my->begin())
		return abs(*pnt - arr[idx].first);
	else
		return min(abs(*pnt - arr[idx].first), abs(arr[idx].first - *prev(pnt)));
}

long long min_total_length(std::vector<int> a, std::vector<int> c) {
	int n = a.size() + c.size();
	arr.push_back({-1, 0});
	for (int x : a) {
		r.push_back(x);
		arr.push_back(pii(x, 1));
	}
	for (int y : c) {
		b.push_back(y);
		arr.push_back(pii(y, -1));
	}
	sort(all(arr));
	vector<int> memo(2*n+1, -1);
	vector<int> lastt(n+1, -1);
	int balance = n;
	memo[n] = 0;
	
	vector<ll> sumr(n+1), sumb(n+1);
	for (int i = 1; i <= n; i++) {
		sumr[i] = sumr[i - 1], sumb[i] = sumb[i - 1];
		if (arr[i].second == 1) {
			sumr[i] += arr[i].first;
			balance++;
		} else {
			sumb[i] += arr[i].first;
			balance--;
		}
		lastt[i] = memo[balance];
		memo[balance] = i;
	}

	vector<ll> dp(n+1);
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1] + dist_to_nearest(i);
		if (lastt[i] != -1)
			dp[i] = min(dp[i], dp[lastt[i]] + abs((sumr[i] - sumr[lastt[i]]) - (sumb[i] - sumb[lastt[i]])));
	}

	return dp[n];
}

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