Submission #582707

#	Time	Username	Problem	Language	Result	Execution time	Memory
582707		Jomnoi	Wiring (IOI17_wiring)	C++17	100 / 100	120 ms	13964 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;

const int MAX_N = 2e5 + 10;
const int INF = 1e9 + 7;

int dist[MAX_N];
long long dp[MAX_N], qs[MAX_N];

long long min_total_length(vector <int> r, vector <int> b) {
	int N = r.size() + b.size();
	int latest[2];
	vector <pair <int, int>> vec;

	vec.emplace_back(-1, -1);
	for(auto p : r) {
		vec.emplace_back(p, 0);
	}
	for(auto p : b) {
		vec.emplace_back(p, 1);
	}
	sort(vec.begin(), vec.end());

	for(int i = 1; i <= N; i++) {
		dist[i] = INF;
	}

	latest[0] = 0, latest[1] = 0;
	for(int i = 1; i <= N; i++) {
		if(latest[vec[i].second ^ 1] != 0) {
			dist[i] = min(dist[i], abs(vec[i].first - vec[latest[vec[i].second ^ 1]].first));
		}
		latest[vec[i].second] = i;
	}

	latest[0] = 0, latest[1] = 0;
	for(int i = N; i >= 1; i--) {
		if(latest[vec[i].second ^ 1] != 0) {
			dist[i] = min(dist[i], abs(vec[i].first - vec[latest[vec[i].second ^ 1]].first));
		}
		latest[vec[i].second] = i;
	}

	int cnt = 0;
	map <int, int> mp;
	mp[0] = 0;
	for(int i = 1; i <= N; i++) {
		qs[i] = qs[i - 1];
		if(vec[i].second == 0) {
			qs[i] += vec[i].first;
			cnt++;
		}
		else { // vec[i].second == 1
			qs[i] -= vec[i].first;
			cnt--;
		}

		dp[i] = dp[i - 1] + dist[i];

		if(mp.count(cnt)) {
			dp[i] = min(dp[i], dp[mp[cnt]] + abs(qs[i] - qs[mp[cnt]]));
		}
		mp[cnt] = i;
	}
	return dp[N];
}

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