Cod sursa(job #522074)

Utilizator andreinsAndrei Nae andreins Data 14 ianuarie 2011 11:08:35
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct CONCERT
{
	int x,y;
};
bool cmp(CONCERT a, CONCERT b)
{
	return ((a.y)<(b.y));
}
CONCERT x[100010];
int t[100010];
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d%d",&x[i].x,&x[i].y);
	sort(x+1,x+n+1,cmp);
	int k=1;
	for(i=1;i<=x[n].y;i++)
	{
		t[i]=t[i-1];
		
		while(i==x[k].y)
		{
			if(t[i]<t[x[k].x]+i-x[k].x)
				t[i]=t[x[k].x]+i-x[k].x;
			k++;
		}
	}
	printf("%d",t[x[n].y]);
	return 0;
}