Submission #313177

#	Time	Username	Problem	Language	Result	Execution time	Memory
313177		tengiz05	Wiring (IOI17_wiring)	C++17	100 / 100	142 ms	16096 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
long long pref[N];
long long dp[N];
vector<pair<long long, bool>> a, R, B;
int getMin(pair<long long, bool> p){
	long long mn = 1e18;
	if(p.second){
		auto it = lower_bound(R.begin(), R.end(), p);
		if(it != R.end())mn = (*it).first-p.first;
		if(it != R.begin()){it--;mn = min(mn, p.first-(*it).first);}
	}else {
		auto it = lower_bound(B.begin(), B.end(), p);
		if(it != B.end())mn = (*it).first-p.first;
		if(it != B.begin()){it--;mn = min(mn, p.first-(*it).first);}
	}return mn;
}
long long min_total_length(vector<int> r, vector<int> b) {
	a.push_back({0,0});
	for(auto x : r)a.push_back({x, 0}), R.push_back({x, 0});
	for(auto x : b)a.push_back({x, 1}), B.push_back({x, 1});
	sort(a.begin(), a.end());
	int n = (int)a.size()-1;
	int cnt = 0;
	map<int, int> m;
	m[0] = 0;
	dp[0] = 0;
	for(int i=1;i<=n;i++){
		pref[i] = pref[i-1] + ((a[i].second)?-a[i].first : a[i].first);
		cnt += a[i].second?-1 : 1;
		dp[i] = dp[i-1] + getMin(a[i]);
		if(cnt == 0 || m[cnt] > 0)dp[i] = min(dp[i], dp[m[cnt]] + abs(pref[i] - pref[m[cnt]]));
		m[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