Cod sursa(job #68412)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 27 iunie 2007 20:17:40
Problema Orase Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;

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

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

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

int main() {
	long i;
	
	freopen(FIN, "r", stdin);
	scanf("%ld %ld", &n, &m);
	for (i=0; i<n; ++i) {
		scanf("%ld %ld", &x, &y);
		A[i] = make_pair(x,abs(y));
	}
	fclose(stdin);
	
	sort(A, A+n, cmp);
	distant = A[0].second ; maxim = 0;
	for (i=1; i<n; ++i) {
		if ( A[i].first==A[i-1].first )
			continue;
		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("%ld\n", maxim);
	fclose(stdout);
	return 0;
}