Cod sursa(job #129436)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 29 ianuarie 2008 15:04:11
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>
#include <stdlib.h>

struct oras {
	long x, h;
};

oras v[50002];

int cmp(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]), cmp);
	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);
}