Cod sursa(job #81338)

Utilizator maria_pparcalabescu maria daniela maria_p Data 1 septembrie 2007 14:57:44
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>

long a[50000],b[50000],d[50000],l[50000],m,n,i,j,q,max,p,k;
void interclasare(long st, long dr, long mij){
	for(i=st;i<=dr;i++){
		a[i]=d[i];
		b[i]=l[i];
	}
	k=st-1;i=st;j=mij+1;
	while(i<=mij && j<=dr)
		if(a[i]<a[j]){
			d[++k]=a[i];
			l[k]=b[i++];
		}
		else{
			d[++k]=a[j];
			l[k]=b[j++];
		}
	for(q=i;q<=mij;q++){
		d[++k]=a[q];
		l[k]=b[q];
	}
	for(q=j;q<=dr;q++){
		d[++k]=a[q];
		l[k]=b[q];
	}
}
void sort(long st, long dr){
	long mij;
	if(st<dr){
		mij=(st+dr)/2;
		sort(st,mij);
		sort(mij+1,dr);
		interclasare(st,dr,mij);
	}
}
int main(){
	freopen("orase.in","r",stdin);
	freopen("orase.out","w",stdout);
	scanf("%ld%ld",&m,&n);
	for(i=0;i<n;i++)
		scanf("%ld%ld",&d[i],&l[i]);
	sort(0,n-1);
	max=l[0];p=0;
	for(i=1;i<n;i++){
		max+=d[i]-d[i-1];
		if(p<max+l[i])
			p=max+l[i];
		if(max<l[i])
			max=l[i];
	}
	printf("%ld\n",p);
	fclose(stdin);
	fclose(stdout);
	return 0;
}