Submission #1061058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061058		vjudge1	Wiring (IOI17_wiring)	C++17	55 / 100	184 ms	12212 KiB

wiring

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

#define ll long long
#define c second
#define pt first
int const N=2e5+5;
ll const inf=1e16;
ll dp[N];
ll n,m;
vector<pair<ll,bool>> al;
ll par[N];
ll pre[N];
ll compute(int l,int r){
	if(l==0||pre[r]==0||l>=r)
		return inf;
	ll mi=pre[r];
	ll y=par[mi]-par[l-1],x=par[r]-par[mi];
	ll max_y=al[mi].pt,min_x=al[mi+1].pt;
	ll cx=r-mi,cy=mi-(l-1);
	ll v=(x-(max_y*cx))+(cy*max_y)-y;
	v+=max(0LL,(cy-cx))*(min_x-max_y);
	v+=min(dp[l],dp[l-1]);
	return v;
}
ll min_total_length(vector<int> r, vector<int> b){
	n=r.size();
	m=b.size();
	al.push_back({-1,0});
	for(int i:r)
		al.push_back({i,0});
	for(int i:b)
		al.push_back({i,1});
	sort(al.begin(), al.end());
	for(int i=1;i<=n+m;i++)
		par[i]=par[i-1]+al[i].pt;
	for(int i=2;i<=n+m;i++){
		if(al[i].c==al[i-1].c)
			pre[i]=pre[i-1];
		else
			pre[i]=i-1;
	}
	for(int i=1;i<=n+m;i++)
		dp[i]=inf;
	for(int i=2;i<=n+m;i++){
		dp[i]=min(compute(pre[i],i),compute(pre[pre[i]]+1,i));
		ll mid=(pre[pre[i]]+pre[i]+1)/2;
		for(int j=min(pre[i],mid+100);j>max(pre[pre[i]],mid-100);j--)
			dp[i]=min(dp[i],compute(j,i));
	}
	return dp[n+m];
}
// int main(){
// 	int nn,mm;
// 	cin>>nn>>mm;
// 	vector<int> rr(nn),bb(mm);
// 	for (int i = 0; i < nn; ++i)
// 		cin>>rr[i];
// 	for (int i = 0; i < mm; ++i)
// 		cin>>bb[i];
// 	cout<<min_total_length(rr,bb)<<endl;
// }

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