Submission #313190

#	Time	Username	Problem	Language	Result	Execution time	Memory
313190		juggernaut	Wiring (IOI17_wiring)	C++14	100 / 100	131 ms	15964 KiB

wiring

#include"wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pref[200005],dp[200005];
vector<pair<ll,bool>>a,r,b;
int getMin(pair<long long,bool>p){
	ll 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;
}
ll 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=a.size()-1,cnt=0,i;
	map<int,int>m;
	m[0]=0;
	dp[0]=0;
	for(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