Cod sursa(job #94322)

Utilizator savimSerban Andrei Stan savim Data 22 octombrie 2007 17:27:58
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
long d[50001],s[50001];
long b[50001],c[50001];
long sol,n,m,i,j,max,poz;
FILE *f1,*f2;
void inter(int p, int r)
{
	int q=(p+r)/2;
	int i=p,j=q+1,t=p-1;

	while (i<=q && j<=r)
	if (d[i]<=d[j])
		{
			t++;
			b[t]=d[i];
			c[t]=s[i];
			i++;
		}
		else
		{
			t++;
			b[t]=d[j];
			c[t]=s[j];
			j++;
		}

   while (i<=q)
   {
		t++;
		b[t]=d[i];
		c[t]=s[i];
		i++;
   }
   while (j<=r)
   {
		t++;
		b[t]=d[j];
		c[t]=s[j];
		j++;
   }
   for (i=p; i<=r; i++)
   {
		d[i]=b[i];
		s[i]=c[i];
   }
}
void merge(int p, int r)
{
	if (p<r)
	{
		int q=(p+r)/2;
		merge(p,q);
		merge(q+1,r);
		inter(p,r);
	}

}
int main()
{
	f1=fopen("orase.in","r");
	f2=fopen("orase.out","w");
	fscanf(f1,"%ld%ld",&m,&n);
	for (i=1; i<=n; i++)
		fscanf(f1,"%ld%ld",&d[i],&s[i]);

	merge(1,n);
	max=0;poz=1;j=0;sol=0;
	for (i=2; i<=n; i++)
	{
		j++;
		if (s[j]-d[j]>max)
		{
			max=s[j]-d[j];
			poz=j;
		}
		if (s[poz]+s[i]+d[i]-d[poz]>sol)
			sol=s[poz]+s[i]+d[i]-d[poz];
	}
	fprintf(f2,"%ld\n",sol);
	fclose(f1);
	fclose(f2);
	return 0;
}