Cod sursa(job #522236)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 14 ianuarie 2011 17:01:17
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct formatie 
{
	int x,y;
};
formatie f[100010];
int t[100010],c[100010];
bool cmp(formatie a,formatie b)
{
	return a.y<b.y;
}
long bs(int a,int b)
{
	int st,dr,med,last=0;
	st=1;
	dr=b;
	while (st<=dr)
	{
		med=(st+dr)/2;
		if (f[med].y<=a)
		{
			last=med;
			st=med+1;
		}
		else
			dr=med-1;
	}
	return last;
}
/*int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int last,max,i,n;
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%ld%ld",&f[i].x,&f[i].y);
	sort(f+1,f+n+1,cmp);
	max=f[n].y;
	last=1;
	for (i=1;i<=max;i++)
	{
		t[i]=t[i-1];
		while (f[last].y==i)
		{
			if (t[i]<t[f[last].x]+i-f[last].x)
				t[i]=t[f[last].x]+i-f[last].x;
			last++;
		}
	}
	printf("%ld",t[max]);
}*/
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int last,max,i,n,poz;
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%ld%ld",&f[i].x,&f[i].y);
	sort(f+1,f+n+1,cmp);
	c[0]=0;c[1]=f[1].y-f[1].x;
	for (i=2;i<=n;i++)
	{
		c[i]=c[i-1];
		poz=bs(f[i].x,i-1);
		if (c[i]<c[poz]+f[i].y-f[i].x)
			c[i]=c[poz]+f[i].y-f[i].x;
	}
	printf("%ld",c[n]);
}