Cod sursa(job #81330)

Utilizator maria_pparcalabescu maria daniela maria_p Data 1 septembrie 2007 14:38:22
Problema Orase Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 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-1;i++)
		if(l[i]+d[i]-d[p]>=max){
			max=l[i];
			p=i;
		}
		else max=max+d[i]-d[i-1];
	max=max+d[n-1]-d[p]+l[n-1];
	printf("%ld\n",max);
	fclose(stdin);
	fclose(stdout);
	return 0;
}