Submission #956925

#	Time	Username	Problem	Language	Result	Execution time	Memory
956925		ZeroCool	Wiring (IOI17_wiring)	C++14	100 / 100	93 ms	15552 KiB

wiring

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

using namespace std;

using ll = long long;
#define pb push_back

#define all(v) v.begin(), v.end()

const int N = 2e5 + 10;

ll pref[N];
ll dp[N];

ll min_total_length(vector<int> r, vector<int> b) {
	vector<pair<ll,ll> > A;

	A.pb({0, -1});

	for(auto u : r)A.pb({u, -1});
	for(auto u : b)A.pb({u, 1});

	sort(all(A));

	int n = A.size();

	int cnt = 0;
	map<int,int> mp;
	for(int i= 1;i<n;i++){
		pref[i] = pref[i-1] + A[i].first * A[i].second;
		cnt += A[i].second;

		ll dist = 1e18;
		if(A[i].second == -1){
			auto it = lower_bound(all(b), A[i].first);
			if(it != b.end())dist = min(dist, *it - A[i].first);;
			if(it != b.begin()){
				it --;
				dist = min(dist, abs(*it - A[i].first));
			}
		}else{
			auto it = lower_bound(all(r), A[i].first);
			if(it != r.end())dist = min(dist, *it - A[i].first);;
			if(it != r.begin()){
				it --;
				dist = min(dist, abs(*it - A[i].first));
			}
		}

		dp[i] = dp[i-1] + dist;
		if(cnt == 0 || mp[cnt] > 0)dp[i] = min(dp[i], dp[mp[cnt]] + abs(pref[i] - pref[mp[cnt]]));
		mp[cnt] = i;
	}
	return dp[n-1];
}

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