Cod sursa(job #521382)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 12 ianuarie 2011 11:38:02
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 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 max=0,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)
	{
		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;
		}
		c[i]=v[i].b-v[i].a+c[last];
		if(c[i]>max)
			max=c[i];
	}
	printf("%ld\n",max);
	return 0;
}