Cod sursa(job #154126)

Utilizator MirageRobert Sandu Mirage Data 10 martie 2008 22:13:20
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<stdio.h>
#include<stdlib.h>
struct muie{
	int d,l;
};
int comp(const void *a,const void *b){
	int *aa=(int *)a, *bb=(int *)b;
	int x=*aa, y=*bb;
	return x-y;
}
int main () {
	int m,n,i,max=-1,a,w[50000];
	muie v[50000];
	freopen("orase.in","r",stdin);
	freopen("orase.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(i=0;i<n;++i)
		scanf("%d%d",&v[i].d,&v[i].l);
	qsort(v,n,sizeof(v[0]),comp);
	for(i=0;i<n;++i)
		if(v[i].l-v[i].d>w[i-1])
			w[i]=v[i].l-v[i].d;
		else
			w[i]=w[i-1];
	for(i=n-1;i>0;--i){
		a=v[i].d+v[i].l+w[i-1];
		if(a>max)
			max=a;
	}
	printf("%d\n",max);
	return 0;
}