Cod sursa(job #154217)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 10 martie 2008 23:53:30
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<stdio.h> 
#include<stdlib.h>
#include<algorithm>
#define N 100010  
using namespace std;
struct interval
{  
    int a,b;  
};
interval v[N];
int pozz[N];
struct timp
{
	int cost,ora;
};
timp best[N];
int compar(interval*aa,interval*bb){  
	if (aa->b<bb->b)  
		return -1;  
	if (aa->b>bb->b)  
		return 1;  
	if (aa->a>bb->a)  
		return 1;  
	if (aa->a<bb->a)  
		return -1;  
	return 0;  
}  
int f_comp(interval x,interval y)
{
	return x.a<y.a;
}
int caut(int p,int u,int x,int n){
	int m;
	while(p<u){
		m=(p+u)/2;
		if(x<=best[m].ora)
			u=m;
		else
			p=m+1;
	}
	if(best[p].ora>x)
		--p;
	return p;
}
int main()
{  
	int n,i,s=0,t,j,x,m=0;
	int poz,p,u,b[N]={0};
	freopen("heavymetal.in","r",stdin);  
	freopen("heavymetal.out","w",stdout);  
	scanf("%d", &n);  
	for (i=0;i<n;++i)
	{  
		scanf("%d%d",&v[i].a, &v[i].b);  
		pozz[i]=i;
	}
		
	best[m].cost=v[pozz[0]].b-v[pozz[0]].a;
	best[m++].ora=v[pozz[0]].b;
	
	for(i=1;i<n;++i)
	{
		poz=caut(0,m-1,v[pozz[i]].a,m);
		if(v[pozz[i]].b == best[m-1].ora)
		{
			if(best[poz].cost+v[pozz[i]].b-v[pozz[i]].a>best[m-1].cost)
				best[m-1].cost=best[poz].cost+v[pozz[i]].b-v[pozz[i]].a;
		}
		else
			if(best[poz].cost+v[pozz[i]].b-v[pozz[i]].a>best[m-1].cost){
				best[m].cost=best[poz].cost+v[pozz[i]].b-v[pozz[i]].a;
				best[m++].ora=v[pozz[i]].b;
			}
	}
	printf("%d\n",best[m-1].cost);
	return 0;  
}