Cod sursa(job #445041)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 22 aprilie 2010 16:22:00
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#include<algorithm>
#define Nmax 100010
#define Max(a,b) a>b ? a : b
using namespace std;

int viz[Nmax],best[Nmax],i,j,n,m,N,K;
struct coord {int poz,val;} crd[Nmax<<1];
struct norm {int x,y,val;} v[Nmax];

int cmp (coord a, coord b)
{
	return a.val<b.val;
}

int cmp1 (norm a, norm b)
{
	return a.y<b.y;
}

int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&v[i].x,&v[i].y);
		
		v[i].val=v[i].y-v[i].x;
		crd[++K].val=v[i].x;
		crd[K].poz=i;
		crd[++K].val=v[i].y;
		crd[K].poz=i;
	}
	
	sort(crd+1,crd+K+1,cmp);
	
	for(i=1;i<=K;i++)
		if(crd[i].val!=crd[i-1].val)
		{
			N++;
			if( v[crd[i].poz].x==crd[i].val) v[crd[i].poz].x=N;
			if( v[crd[i].poz].y==crd[i].val) v[crd[i].poz].y=N;
		}
	
	sort(v+1,v+n+1,cmp1);	
	
	for(i=1;i<=n;i++)
		if(v[i].y!=v[i-1].y) viz[v[i].y]=i;
	
	for(i=1;i<=N;i++)
		if(!viz[i]) best[i]=best[i-1];
	else
	{
		for(j=viz[i];v[j].y==i;j++)
			best[i]=Max(best[i],best[v[j].x]+v[j].val);
	}
	
	printf("%d",best[N]);
	return 0;
}