Cod sursa(job #74285)

Utilizator swift90Ionut Bogdanescu swift90 Data 24 iulie 2007 17:01:22
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int, int> per[50010];
int main(){
	freopen("orase.in","r",stdin);
	freopen("orase.out","w",stdout);
	int m,n,i,max=0,dmax=0,aux;
	scanf("%d %d",&m,&n);
	for(i=0;i<n;i++)
		scanf("%d %d",&per[i].first, &per[i].second);
	sort(per, per+n);
	max=per[0].second-per[0].first;
	if(n==1){
		printf("0\n");
		return 0;
	}
	
	dmax=per[1].first+per[1].second+max;
	for(i=1;i<n;i++){
		aux=per[i-1].second-per[i-1].first;
		if(aux>max)
			max=aux;
		aux=per[i].first+per[i].second;
		if(aux+max>dmax)
			dmax=aux+max;
	}
	
	printf("%d\n",dmax);
	
	return 0;
}