Cod sursa(job #372933)

Utilizator alutzuAlexandru Stoica alutzu Data 12 decembrie 2009 10:34:01
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<cstdio>
#include<algorithm>

using namespace std ;

struct qq { int x , y ; };
const int NMAX = 50005 ;
qq s [ NMAX ] ;

bool comp ( qq a , qq b )
{
	return ( a.x < b.x ) ;
}

int main ( )
{
	
	freopen ( "orase.in" , "r" , stdin ) ;
	freopen ( "orase.out" , "w" , stdout ) ;
	
	int n , m , i ;
	int var , max = 0 , last ;
	
	scanf ( "%d%d" , &m , & n ) ;
	
	for ( i = 1 ; i <= n ; i ++ )
		scanf ( "%d%d" , & s[i].x , & s[i].y ) ;
	
	sort ( s + 1 , s + n + 1 , comp ) ;
	
	last = 1 ;
	for ( i = 2 ; i <= n ; i ++ )
	{
		//vedem daca pastram orasul 1; sau alegem alt oras
		if ( s[last].y + s[i].x - s[last].x < s[i].y )
			//schimba referinta
		{
			last=i;
			if ( s[i].y > max ) max = s[i].y ;
		}			
		var = s[last].y + s[i].x - s[last].x + s[i].y ;
		if ( var > max )
			max = var;
	}
	
	printf ( "%d" , max ) ;
	
	return 0 ;
}