Cod sursa(job #515385)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 21 decembrie 2010 12:46:02
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

FILE*f=fopen("heavymetal.in","r");
FILE*g=fopen("heavymetal.out","w");

int N,i,p,u,m,S[100005];

struct interv{
	int a;
	int b;
}W[100005];

int cmp(interv a,interv b){
	if ( a.b != b.b )
		return a.b < b.b;
	return a.a < b.a;
}

int main () {
	
	fscanf(f,"%d",&N);
	for ( i = 1 ; i <= N ; ++i )
		fscanf(f,"%d %d",&W[i].a,&W[i].b);
	
	sort(W+1,W+N+1,cmp);
	
	for ( i = 1 ; i <= N ; ++i ){
		
		p = 0 ; u = i - 1;
		while ( p <= u ){
			m = p + (u - p) / 2;
			if ( W[m].b > W[i].a )
				u = m - 1;
			else
				p = m + 1;
			
		}
		if ( W[i].b - W[i]. a  + S[ u ] > S[i-1] )
			S[i] = W[i].b - W[i]. a  + S[ u ];
		else
			S[i] = S[i-1];
		
	}
	
	fprintf(g,"%d\n",S[N]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}