Cod sursa(job #160678)

Utilizator hadesgamesTache Alexandru hadesgames Data 16 martie 2008 16:46:13
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#include <stdlib.h>
struct ceva
{
	int a,b;
};
struct ceva2
{
	int a,o;
};
ceva a[100000];
ceva2 b[100000];
int m;
int compare(const void *a,const void *b)
{
	ceva *aa=(ceva*)a;
	ceva *bb=(ceva*)b;
	if (aa->b<bb->b)
		return -1;
	if (aa->b>bb->b)
		return 1;
	return 0;
}
int cauta(int x)
{
	int p=1,u=m,y;
	while (p<u)
	{
		y=(u+p)/2;
		if (x<=b[y].o)
			u=y;
		else
			p=y+1;
	}
	if (b[u].o<=x)
		return u;
	else
		return u-1;
}
int main()
{
	FILE *in,*out;
	int n,max=0,t,i;
	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);
	}
	qsort(a+1,n,sizeof(a[1]),compare);
	m=0;
	for (i=1;i<=n;i++)
	{
		t=cauta(a[i].a);
		if (a[i].b!=b[m].o)
			m++;
		b[m].o=a[i].b;
		if (b[t].a+a[i].b-a[i].a>b[m].a)
		{
			b[m].a=b[t].a+a[i].b-a[i].a;
		}
		if (max<b[m].a)
			max=b[m].a;
	}
	fprintf(out,"%d\n",max);
	fclose(in);
	fclose(out);
	return 0;
}