Cod sursa(job #152332)

Utilizator hadesgamesTache Alexandru hadesgames Data 9 martie 2008 13:05:17
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#include <stdlib.h>
struct ceva
{
	int a,b;
};
ceva a[100000];
int e[100000];
int b[100000];
int compare(const void *b,const void *c)
{
	int *aa=(int*)b;
	int *bb=(int*)c;
	if (a[*aa].b<a[*bb].b)
		return -1;
	if (a[*aa].b>a[*bb].b)
		return 1;
	return 0;
}
int main()
{
	FILE *in,*out;
	int n,i,j,x,t,max;
	in=fopen("heavymetal.in","r");
	out=fopen("heavymetal.out","w");
	fscanf(in,"%d",&n);
	for (i=1;i<=n;i++)
	{
		fscanf(in,"%d%d",&a[i].a,&a[i].b);
		e[i]=i;
	}
	qsort(e+1,n,sizeof(e[1]),compare);
 	max=0;
	for (i=1;i<=n;i++)
	{
		b[i]=a[e[i]].b-a[e[i]].a;
		j=i-1;
		x=1;
		while (j>0&&x)
		{
			if (a[e[j]].b>a[e[i]].a)
				t=b[j];
			else
				t=b[j]+a[e[i]].b-a[e[i]].a;
			if(t>b[i])
				b[i]=t;
			if (a[e[j]].b<=a[e[i]].a)
				x=0;
			j--;
			
		}
		if (b[i]>max)
			max=b[i];
	}
	fprintf(out,"%d\n",max);
	fclose(in);
	fclose(out);
	return 0;
	
}