Cod sursa(job #522087)

Utilizator cahemanCasian Patrascanu caheman Data 14 ianuarie 2011 11:43:15
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#include<stdlib.h>
inline long max(long c,long b)
{
	if(b>=c)
		return b;
	return c;
}	
struct casy
{
long x,y;
};
casy a[100011];
long cost[100011];
long cb(long dr,long c)
{
long last=0,st,m;	
st=1;
while(st<=dr)
{
m=(st+dr)>>1;
if(a[m].y<=c)
{
	last=m;
	st=m+1;
}
else
	dr=m-1;
}
return last;
}
int comp(const void *c,const void *b)
{
	casy *pc,*pb;
	pc=(casy*)c;
	pb=(casy*)b;
	if(pc->y>pb->y)
		return 1;
	if(pc->y==pb->y)
		return 0;
	return -1;
}	
bool comp2(casy a,casy b)
{
	return a.y<b.y;
}	
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	long n,i;
	scanf("%ld",&n);
	for(i=1;i<=n;i++)
		scanf("%ld%ld",&a[i].x,&a[i].y);
	//qsort(a+1,n,sizeof(a[0]),comp);
	sort(a+1,a+n+1,comp2);
	cost[1]=a[1].y-a[1].x;
	for(i=2;i<=n;i++)
		cost[i]=max(cost[i-1],a[i].y-a[i].x+cost[cb(i-1,a[i].x)]);
	printf("%ld\n",cost[n]);
	return 0;
}