Cod sursa(job #143662)

Utilizator znakeuJurba Andrei znakeu Data 26 februarie 2008 19:08:53
Problema Orase Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#include <stdlib.h>

struct oras
{
	int d,l;	
};
oras v[50001];

int comp(const void *a, const void *b)
{
	oras *aa=(oras*) a, *bb=(oras*) b;
	oras x=*aa, y=*bb;
	if (x.d<y.d)
		return -1;
	if (x.d>y.d)
		return 1;
	return 0;
}

int main()
{
	int i,j,m,n,max=0,maxt=0;
	
	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;
}