Cod sursa(job #551454)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 10 martie 2011 19:54:48
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<stdio.h>
#include<algorithm>
#define Nmax 100010
using namespace std;

struct interval { int x,y ; } v[Nmax] ; 
int i,n,best[Nmax],j;

int cmp ( interval a, interval b ) 
{
	return a.y < b.x ;
}

int bsearch( int x ) 
{
	int s = 0 , d = i , m , r = 0 ;
	
	for( m = (s+d)>>1 ; s <= d ; m = (s+d)>>1 ) 
		if( v[m].y <= x ) { r = m ; s = m + 1 ; } 
		else d = m - 1 ; 
	
	return r ; 
}

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);
	
	sort( v+1 , v+n+1, cmp ) ;
	
	for( i = 1 ; i <= n ; i++ ) 
	{
		best[i] = best[i-1];
		j = bsearch(v[i].x);
		
		if( best[i] < best[j] + v[i].y - v[i].x )
			best[i] = best[j] + v[i].y - v[i].x ; 
	}
	
	printf("%d",best[n]);
	
	return 0; 
}