Submission #59167

#	Time	Username	Problem	Language	Result	Execution time	Memory
59167		TadijaSebez	Wiring (IOI17_wiring)	C++11	100 / 100	95 ms	102528 KiB

wiring

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
const int N=200050;
const ll inf=1e18;
pair<int,int> a[N];
ll dp[N],f[N];
int last[2],cnt[N];
ll max(ll a, ll b){ return a>b?a:b;}
ll min(ll a, ll b){ return a>b?b:a;}
ll min_total_length(vector<int> r, vector<int> b)
{
	int i,j,n;n=r.size()+b.size();
	for(i=0;i<r.size();i++) a[i+1]=mp(r[i],0);
	for(i=0;i<b.size();i++) a[i+1+r.size()]=mp(b[i],1);
	sort(a+1,a+1+n);a[0].second=2;
	bool ok;ll sum=0;last[0]=last[1]=0;
	for(i=1;i<=n;i++)
	{
		dp[i]=inf;
		if(!last[a[i].second^1]){ last[a[i].second]=i;continue;}
		//printf("%i %i %i\n",i,last[0],last[1]);
		if(a[i].second!=a[i-1].second)
		{
			//printf("->%i<-\n",i);
			ll cost=0;
			dp[i]=dp[i-1]+a[i].first-a[i-1].first;
			for(j=i-1;j>last[a[i].second];j--)
			{
				cost+=a[i].first-a[j].first;
				f[j]=dp[j-1]+cost;
				if(dp[i]>=dp[j-1]+cost)
				{
					cnt[i]=i-j;
					dp[i]=dp[j-1]+cost;
				}
			}
			for(j=last[a[i].second]+2;j<i;j++) f[j]=min(f[j],f[j-1]);//,printf("%i %lld\n",j,f[j]);
			ok=1;sum=0;
		}
		else
		{
			sum+=a[i].first-a[last[a[i].second^1]+1].first;
			dp[i]=min(dp[i],dp[i-1]+a[i].first-a[last[a[i].second^1]].first);
			int sz=i-last[a[i].second^1];
			if(ok && a[last[a[i].second^1]-sz+1].second==(a[i].second^1))
			{
				dp[i]=min(dp[i],f[last[a[i].second^1]-sz+1]+sum);//dp[last[a[i].second^1]-sz-1]+a[i].first-a[last[a[i].second^1]-sz].first);
				//printf("%i %lld %lld\n",a[i].first,f[last[a[i].second^1]-sz+1],sum);
			}
			else ok=0;
			/*if(cnt[i-1]>=i-last[a[i].second^1])
			{
				cnt[i]=cnt[i-1];
				dp[i]=dp[i-1]+a[i].first-a[last[a[i].second^1]+1].first;
			}
			else
			{
				if(a[last[a[i].second^1]-cnt[i-1]].second==(a[i].second^1))
				{
					if(dp[last[a[i].second^1]-cnt[i-1]-1]+a[i].first-a[last[a[i].second^1]-cnt[i-1]].first<dp[i])
					{
						dp[i]=dp[last[a[i].second^1]-cnt[i-1]-1]+a[i].first-a[last[a[i].second^1]-cnt[i-1]].first;
						cnt[i]=cnt[i-1]+1;
					}
				}
				if(dp[i-1]+a[i].first-a[last[a[i].second^1]].first<dp[i])
				{
					dp[i]=dp[i-1]+a[i].first-a[last[a[i].second^1]].first;
					cnt[i]=cnt[i-1];
				}
			}*/
		}
		last[a[i].second]=i;
		//printf("%lld ",dp[i]);
	}
	return dp[n];
}
/*int main()
{
	int n,m,i,x;vector<int> r,b;
	scanf("%i %i",&n,&m);
	for(i=0;i<n;i++) scanf("%i",&x),r.pb(x);
	for(i=0;i<m;i++) scanf("%i",&x),b.pb(x);
	printf("%lld\n",min_total_length(r,b));
	return 0;
}*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:18:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<r.size();i++) a[i+1]=mp(r[i],0);
          ~^~~~~~~~~
wiring.cpp:19:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<b.size();i++) a[i+1+r.size()]=mp(b[i],1);
          ~^~~~~~~~~
wiring.cpp:50:4: warning: 'ok' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(ok && a[last[a[i].second^1]-sz+1].second==(a[i].second^1))
    ^~

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