Cod sursa(job #344119)

Utilizator marinaMarina Horlescu marina Data 28 august 2009 15:07:20
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
//Orase - preONI 2007 Runda Finala [infoarena]

#include <stdio.h>
#include <algorithm>

using namespace std;

const char input[] = "orase.in";
const char output[] = "orase.out";

struct grup
{
	int d, l;
};

struct cmp
{
	bool operator() (const grup &a, const grup &b) const
	{
		return a.d < b.d;
	}
};

int main()
{
	freopen(input, "r", stdin);
	freopen(output, "w", stdout);
	
	int m, n;
	scanf("%d %d", &m, &n);
	
	grup *v = new grup[n];
	int i;
	for(i = 0; i < n; ++i)
		scanf("%d %d", &v[i].d, &v[i].l);
	
	sort(v, v + n, cmp());
	
	int dMax = 0, dprev = 0;
	for(i = 0; i < n; ++i)
	{
		if(dprev + v[i].l > dMax) dMax = dprev + v[i].l;
		if(dprev < v[i].l) dprev = v[i].l;
		if(i < n-1) dprev += v[i+1].d - v[i].d;
	}
	
	printf("%d\n", dMax);
	return 0;
}