Cod sursa(job #518674)

Utilizator bog29Antohi Bogdan bog29 Data 2 ianuarie 2011 17:48:19
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<fstream>
#define dmax 50004
using namespace std;
ifstream in("orase.in");
ofstream out("orase.out");

int n,m,mx,sol;

struct strada
{	int l;
	int d;
}	s[dmax];

int sf(struct strada a, struct strada b)
{	if(a.d != b.d)
		return (a.d <= b.d);
	return a.l <= b.l;
}	

int main()
{	int i;
	in>>m>>n;
	
	for(i=0;i<n;i++)
		in>>s[i].d>>s[i].l;
	
	in.close();
	
	sort( s, s+n, sf );
	mx=sol=0;
	
	for(i=0;i<n;i++)
	{	
		mx+=(s[i].d - s[i-1].d);
		
		if(mx + s[i].l > sol)
			sol=mx + s[i].l;
	
		if( s[i].l > mx)
			mx=s[i].l;
	}
	out<<sol;
	
	out.close();
	return 0;
}