Cod sursa(job #68422)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 27 iunie 2007 20:41:04
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define FIN "orase.in"
#define FOUT "orase.out"
#define MAX 100020

struct point {
		long first, second;
} A[MAX];
bool cmp( point a, point b ) {
	if ( a.first!=b.first )
		return a.first<b.first;
	else 
		return a.second>b.second;
}

long n,m,x,y;
long long distant, maxim;

int main() {
	long i;
	
	freopen(FIN, "r", stdin);
	scanf("%ld %ld", &m, &n);
/*	if ( n>50000 ) {
		printf("PROST");
		return 50;
	}*/
	for (i=0; i<n; ++i) {
		scanf("%ld %ld", &x, &y);
		A[i].first = x;
		A[i].second = abs(y);
	}
	fclose(stdin);
	
	sort(A, A+n, cmp);
	distant = A[0].second ; maxim = 0;
	for (i=1; i<n; ++i) {
		distant += A[i].first - A[i-1].first;
		if ( maxim < distant + A[i].second )
			maxim = distant + A[i].second;
		if ( distant < A[i].second ) 
			distant = A[i].second;
	}
	
	
	freopen(FOUT, "w", stdout);
	printf("%lld\n", maxim);
	fclose(stdout);
	return 0;
}