Cod sursa(job #140656)

Utilizator za_wolfpalianos cristian za_wolf Data 22 februarie 2008 01:57:57
Problema Heavy metal Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<stdio.h>
//#include<algorithm>
#define NMAX 101001
//using namespace std;
long p,i,y[NMAX],poz,in,sf,a,j,k,l,n,m,q;
struct kkt
{
	long X,Y;
};
kkt x[NMAX],aux;
/*int cmpf(const kkt a,const kkt b)
{
	return a.Y>b.Y;
} */
long mx(long a,long b)
{
	if (a>b) return a;
	return b;
}
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%ld%ld",&x[i].X,&x[i].Y);
	a=1;
	while (a)
	{
		a=0;
		for (i=1;i<n;i++)
			if ((x[i].Y>x[i+1].Y)||(x[i].Y==x[i+1].Y&&x[i].X<x[i+1].X))
			{
				aux=x[i];
				x[i]=x[i+1];
				x[i+1]=aux;
				a=1;
			}
	}

/*	for (i=1;i<=10;i++)
	{
		y[i]=y[i-1];

		for (j=1;j<=n;j++)
			if (x[j].Y==i)



					y[i]=mx(y[i],y[x[j].X]+(x[j].Y-x[j].X));


		if (y[i]>p)
			p=y[i];
	}
	printf("%ld\n",p); */

//	sort(x+1,x+n+1,cmpf);
	for (i=1;i<=n;i++)
	{
		y[x[i].Y]=y[x[i-1].Y];
		if (x[i].X>=x[i-1].Y)
			y[x[i].X]=mx(y[x[i].X],y[x[i-1].Y]);
		else
		if (x[i].X>=x[i-1].X)
			y[x[i].X]=mx(y[x[i].X],y[x[i-1].X]);
		for (j=1;j<=n;j++)
			if (x[j].Y==x[i].Y)
			{
				y[x[i].Y]=mx(y[x[i].Y],y[x[j].X]+(x[j].Y-x[j].X));
				if (x[i].X>=x[j].Y)
					y[x[i].X]=mx(y[x[i].X],y[x[j].Y]);
				else
				if (x[i].X>=x[j].X)
					y[x[i].X]=mx(y[x[i].X],y[x[j].X]);

			}

		if (y[x[i].Y]>p)
			p=y[x[i].Y];
	}
	printf("%ld\n",p);

	return 0;
}