Cod sursa(job #358710)

Utilizator indestructiblecont de teste indestructible Data 24 octombrie 2009 10:37:09
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#include <stdlib.h>
#define N 1<<17
struct pereche
{
	int a,b;
};
pereche v[N];
int n,val;
int best[N];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d%d",&v[i].a,&v[i].b);
}
int compar(const void *p,const void *q)
{
	pereche x=*(pereche*)p;
	pereche y=*(pereche*)q;
	if (x.a<y.a)
		return -1;
	if (x.a>y.a)
		return 1;
	if (x.b<y.b)
		return -1;
	if (x.b>y.b)
		return 1;
	return 0;
}
inline int maxim(int a,int b)
{
	return a>b ? a: b;
}
void solve()
{
	int i,j;
	for (i=1; i<=n; i++)
	{
		if (best[v[i].b]<best[v[i].a]+v[i].b-v[i].a)
		{
			best[v[i].b]=best[v[i].a]+v[i].b-v[i].a;
			for (j=v[i].b; j<=1000; j++)
				best[j]=best[v[i].b];
		}
	}
	printf("%d\n",best[1000]);
}
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	read();
	qsort(v+1,n,sizeof(v[0]),compar);
	solve();
	return 0;
}