Cod sursa(job #748567)

Utilizator cahemanCasian Patrascanu caheman Data 13 mai 2012 19:52:20
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
inline long max(long d,long b)
{
	if(b>=d)
		return b;
	return d;
}   
struct pozdy
{
	long x,y;
};
pozdy a[100011];
long c[100011];
long cb(long dr,long curent)
{
	long l=0,st,med;   
	st=1;
	while(st<=dr)
	{
		med=(st+dr)>>1;
		if(c[med].y<=curent)
		{
			l=med;
			st=med+1;
		}
		else
			dr=med-1;
	}
	return l;
}
int comp(pozdy d,pozdy e)
{
	if(d.y>e.y)
		return 0;
	return 1;
}      
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);
	sort(a+1,a+n+1,comp);
	c[1]=a[1].y-a[1].x;
	for(i=2;i<=n;i++)
		c[i]=max(c[i-1],a[i].y-a[i].x+c[cb(i-1,a[i].x)]);
	printf("%ld\n",c[n]);
	return 0;
}