Cod sursa(job #521383)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 12 ianuarie 2011 11:50:40
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>
#include<stdlib.h>

struct bob
{long a,b;};

bob v[100010];
long c[100010];


int comp(const void *a,const void *b)
{
	bob *x,*y;
	x=(bob*)a;
	y=(bob*)b;
	if(x->b-y->b==0)
		return 0;
	if(x->b-y->b>0)
		return 1;
	return -1;
}


int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	long n,i,st,dr,last,med;
	scanf("%ld",&n);
	for(i=1;i<=n;++i)
		scanf("%ld%ld",&v[i].a,&v[i].b);
	qsort(v+1,n,sizeof(v[0]),comp);
	for(i=1;i<=n;++i)
	{
		c[i]=c[i-1];
		last=0;
		st=1;
		dr=i-1;
		while(st<=dr)
		{
			med=(st+dr)>>1;
			if(v[med].b<=v[i].a)
			{
				last=med;
				st=med+1;
			}
			else
				dr=med-1;
		}
		if(v[i].b-v[i].a+c[last]>c[i])
			c[i]=v[i].b-v[i].a+c[last];
	}
	printf("%ld\n",c[n]);
	return 0;
}