Cod sursa(job #522042)

Utilizator gegeadDragos Gegea gegead Data 14 ianuarie 2011 10:14:49
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int t[100001];
struct concert
{
	int a;
	int b;
};
concert v[100001];

bool cmp(concert a,concert b)
{
	return a.b<b.b;
}



int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int n,i,s,k;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d%d",&v[i].a,&v[i].b);
	sort(v+1,v+n+1,cmp);
	k=1;
	for(i=1;i<=v[n].b;++i)
	{
		t[i]=t[i-1];
		while(v[k].b==i)
		{
			s=v[k].b-v[k].a+t[v[k].a];
			if(s>t[i])
				t[i]=s;
			++k;
		}
	}
	printf("%d",t[v[n].b]);
	return 0;
}