Cod sursa(job #152348)

Utilizator hadesgamesTache Alexandru hadesgames Data 9 martie 2008 13:16:43
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 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,y;
	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;
	y=0;
	for (i=1;i<=n;i++)
	{
		while(a[e[y+1]].b<=a[e[i]].a)
			y++;
		b[i]=a[e[i]].b-a[e[i]].a+b[y];
		if (b[i]>max)
			max=b[i];
	}
	fprintf(out,"%d\n",max);
	fclose(in);
	fclose(out);
	return 0;
	
}