Cod sursa(job #160852)

Utilizator AndreyPAndrei Poenaru AndreyP Data 17 martie 2008 08:10:54
Problema Heavy metal Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>
#include<stdlib.h>
struct interval
{
	int a,b;
};
int best[1000000];
interval v[100000];
int compar(const void*p,const void*q){
	interval *pp=(interval*)p, *qq=(interval*)q;
	interval u=*pp,w=*qq;
	if(u.b<w.b)
		return -1;
	if(u.b>w.b)
		return 1;
	return u.a-w.a;
}
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int n,i,x,j=0,aux;
	scanf("%d",&n);
	for(i=0; i<n; i++)
	{
		scanf("%d%d",&v[i].a,&v[i].b);
	}
	qsort(v,n,sizeof(v[0]),compar);
	/*for(i=0; i<n; i++)
	{
		printf("%d %d\n",v[i].a,v[i].b);
	}*/
	x=v[n-1].b;
	for(i=1; i<=x; i++)
	{
		best[i]=best[i-1];
		while(i==v[j].b)
		{
			aux=best[v[j].a]+v[j].b-v[j].a;
			if(aux>best[i])
				best[i]=aux;
			j++;
		}
		/*if(best[i]>max)
			max=best[i];*/
	}
	printf("%d\n",best[x]);
	return 0;
}