Cod sursa(job #473240)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 28 iulie 2010 14:40:35
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
#include<algorithm>
using namespace std ;

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

long long i,L,X,N,m,p,u,pas,maxx,z,sum ;
char ho ;

struct oaie {
	
	int dist ;
	
	int lana ;
	
} w[100100] ;

int cmp ( oaie a , oaie b ) {
	
	return a.dist > b.dist ; 
	
}

int main () {
	
	fscanf ( f , "%lld %lld %lld" , &N , &X , &L ) ;
	
	for ( i = 1 ; i <= N ; ++i ) {
		
		fscanf ( f , "%d %d " , &w[i].dist , &w[i].lana ) ;
		
	}
	
	sort ( w + 1 , w + N + 1 , cmp ) ;
	
	pas = 0 ;
	
	z = 1 ;
	
	while ( !ho ) {
		
		p = 1 ; u = N ; 
		
		++pas ;
		
		while ( p <= u ) {
			
			m = p + ( u - p ) / 2 ;
			
			if ( w[ m ] . dist + pas * L <= X )
				u = m - 1 ;
			else
				p = m + 1 ;
			
		}
		
		// pozitia ramane in u 
		
		maxx = 0 ;
		
		for ( i = z ; i <= u ; ++ i )
			if ( w[i] . lana > maxx )
				maxx = w[i] . lana ;
		
		sum += maxx ;
		
		z = u + 1 ;
		
		if ( u == N )
			ho = 1 ;
		
	}
	
	fprintf ( g , "%lld\n" , sum ) ;
	
	
	fclose(f);
	fclose(g);
	
	return 0 ; 

}