Submission #142841

#	Time	Username	Problem	Language	Result	Execution time	Memory
142841		babo	Wiring (IOI17_wiring)	C++14	100 / 100	109 ms	19576 KiB

wiring

#include <bits/stdc++.h>
#define inf 2000000000
#define all(x) (x).begin(),(x).end()
#define L long long

using namespace std;

struct S{
	L loc,det,chk,lev,milen;
}a[200020];
L dp[200020];
 
vector<L>v[200020];
L n,m;

L min_total_length(vector<int>r, vector<int>b){
	sort(all(r));
	sort(all(b));
	n=r.size();
	m=b.size();
	L i,ret=0;
	for(i=0;i<n;i++)
	{
		a[i]=(S){r[i],1,0};
	}
	for(i=n;i<n+m;i++)
	{
		a[i]=(S){b[i-n],2,0};
	}
	sort(a,a+n+m,[](S a,S b){
		return a.loc<b.loc;
	});

	L lev=100010;
	for(i=0;i<n+m;i++)
	{
		a[i].lev=lev;
		v[lev].push_back(i);
		if(a[i].det==1&&a[i+1].det==1) lev++;
		if(a[i].det==2&&a[i+1].det==2) lev--;
		//printf("%lld %lld\n",a[i].det,a[i].loc);
	}

	for(i=0;i<n+m;i++)
	{
		L mi=inf;
		vector<int>::iterator it;
		if(a[i].det==1)
		{
			it=lower_bound(all(b),a[i].loc);
			if(it!=b.end())
				mi=min(mi,*it-a[i].loc);
			it=upper_bound(all(b),a[i].loc);
			if(it!=b.begin())
				mi=min(mi,a[i].loc-*(prev(it)));
		}
		else
		{
			it=lower_bound(all(r),a[i].loc);
			if(it!=r.end())
				mi=min(mi,*it-a[i].loc);
			it=upper_bound(all(r),a[i].loc);
			if(it!=r.begin())
				mi=min(mi,a[i].loc-*(prev(it)));
		}
		a[i].milen=mi;
		//printf("%lld ",a[i].milen);
	}
	//puts("");
	for(lev=0;lev<200020;lev++)
	{	
		for(i=0;i<=v[lev].size();i++)
			dp[i]=inf;
		dp[0]=0;
		for(i=0;i<=v[lev].size();i++)
		{
			if(i>=2) dp[i]=min(dp[i],dp[i-2]+a[v[lev][i-1]].loc-a[v[lev][i-2]].loc);
			if(i>=1) dp[i]=min(dp[i],dp[i-1]+a[v[lev][i-1]].milen);
			if(i>=2) dp[i]=min(dp[i],dp[i-2]+a[v[lev][i-1]].loc-a[v[lev][i-2]].loc);
		}
		//for(i=0;i<=v[lev].size();i++)
		//	printf("%lld %lld\n",dp[i][0],dp[i][1]);
		ret+=dp[v[lev].size()];
	}
	return ret;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:72:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<=v[lev].size();i++)
           ~^~~~~~~~~~~~~~~
wiring.cpp:75:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<=v[lev].size();i++)
           ~^~~~~~~~~~~~~~~

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