Cod sursa(job #139307)

Utilizator za_wolfpalianos cristian za_wolf Data 19 februarie 2008 22:34:57
Problema Orase Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 50001
using namespace std;
long n,m,a,i,s,max,k,l,q;
struct kkt
{
	long X,Y;
};
kkt x[NMAX];
int cmpf(const kkt a,const kkt b)
{
	return a.X>b.X;
}
int main()
{
	freopen("orase.in","r",stdin);
	freopen("orase.out","w",stdout);
	scanf("%ld%ld",&m,&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].X>x[i+1].X)
		{
			a=x[i].X;
			x[i].X=x[i+1].X;
			x[i+1].X=a;
			a=x[i].Y;
			x[i].Y=x[i+1].Y;
			x[i+1].Y=a;
			a=1;
		}
	} */
	sort(x+1,x+n+1,cmpf);
	s=x[1].X+x[1].Y;
	max=-1;
	for (i=2;i<=n;i++)
	{
		if (max<s+x[i].X-x[i-1].X+x[i].Y)
			max=s+x[i].X-x[i-1].X+x[i].Y;
		if (s+x[i].X-x[i-1].X<x[i].Y)
			s=x[i].Y;
		else
		s+=(x[i].X-x[i-1].X);
	}
	printf("%ld\n",max);


	return 0;
}