Cod sursa(job #522069)

Utilizator redls_95Nechita Laura redls_95 Data 14 ianuarie 2011 10:53:43
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct point
{
	int x,y;
};
point a1[100002];
int t[1000002];
bool comp(point a,point b)
{
	return a.y<b.y;
}
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int n,i,p;
		scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d%d",&a1[i].x,&a1[i].y);
	sort(a1+1,a1+n+1,comp);
	t[a1[1].y]=a1[1].y-a1[1].x;
	p=2;
	for(i=a1[1].y+1;i<=a1[n].y;i++)
	{
		t[i]=t[i-1];
		if (i==a1[p].y)
		{
			for(;p<=n&& a1[p].y==i;p++)
			{
				if(t[i]<t[a1[p].x]+i-a1[p].x) 
					{
						t[i]=t[a1[p].x]+i-a1[p].x;
					}
			}
		}
		
	}
	printf("%d",t[a1[n].y]);
	return 0;
}