Cod sursa(job #143672)

Utilizator znakeuJurba Andrei znakeu Data 26 februarie 2008 19:17:34
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 50001
struct oras
{
	int d,l;	
};

int comp(const void *a, const void *b)
{
	oras x=*(oras*) a, y=*(oras*) b;
	return x.d-y.d;
}

int main()
{
	int i,m,n,max=0,maxt=0;
	oras v[MAXN];
	
	FILE *in  = fopen("orase.in","r");
	FILE *out = fopen("orase.out","w");
	
	fscanf(in,"%d%d",&m,&n);
	for (i=0; i<n; i++)
		fscanf(in,"%d%d",&v[i].d,&v[i].l);
	
	qsort(v,n,sizeof(v[0]),comp);
	
	max=v[1].d-v[0].d+v[0].l+v[1].l;
	if (v[0].l+v[1].d-v[0].d>v[1].l)
		maxt=v[0].l+v[1].d-v[0].d;
	else
		maxt=v[1].l;
	
	for (i=2; i<n; i++)
	{
		maxt+=v[i].d-v[i-1].d;
		if (maxt+v[i].l>max)
			max=maxt+v[i].l;
		if (v[i].l>maxt)
			maxt=v[i].l;		
	}
	
	fprintf(out,"%d\n",max);
	fclose(in);	
	fclose(out);
	return 0;
}