Cod sursa(job #77092)

Utilizator marius135Dumitran Adrian Marius marius135 Data 13 august 2007 00:27:23
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<stdio.h>
#include<stdlib.h>

struct oras{long x,h;};

oras v[50002];

int sort(const void *a,const void *b)
{
	return (*(oras *)a).x-(*(oras *)b).x;
}
int main()
{
	long m,n,i,val,sol=0,minx,minh;
	
	freopen("orase.in","r",stdin);
	freopen("orase.out","w",stdout);
	
	scanf("%ld %ld",&m,&n);
	for(i=1;i<=n;i++)
		scanf("%ld %ld",&v[i].x,&v[i].h);
	qsort(v+1,n,sizeof(v[0]),sort);
	minx = 1000000;
	minh = 0; 
	for(i=1;i<=n;i++)
	{
		long val = v[i].h +minh + v[i].x - minx;
		if(val > sol) sol = val;
		if(v[i].h - minh  > v[i].x - minx)
		{
			minx = v[i].x;
			minh = v[i].h;
		}
		
	}
	printf("%ld\n",sol);
}