Cod sursa(job #491915)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 12 octombrie 2010 20:01:38
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

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

int N,X,L,dist,i,Tmax,heap[100100],k,j,c,p;
long long smax;

struct oaie {
	int t;
	int lana;
} A[100100];

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

int main () {
	
	fscanf(f,"%d %d %d",&N,&X,&L);
	for ( i = 1 ; i <= N ; ++i ){
		fscanf(f,"%d %d",&dist,&A[i].lana);
		A[i].t = (X - dist)/L + 1 ;
		if ( A[i].t > Tmax)
			Tmax = A[i].t;
	}
	sort(A+1, A+N+1,cmp);
	j = 1;
	for ( i = Tmax; i >= 1 ; --i ){
		
		while ( A[j].t == i ) {
			
			heap[++k] = A[j].lana ; c = k ; p = k / 2;
			
			while ( p != 0 && heap[c] > heap[p] ){
				swap(heap[c],heap[p]);
				c = p ;
				p = p / 2;
			}
			++j;
		}
		
		smax = smax + heap[1];
		
		heap[1] = heap[k--];
		
		p = 1 ; c = 2 * p;
		while ( c <= k ) {
			
			if ( c + 1 <= k && heap[c+1] > heap[c] )
				++c;
			
			if ( heap[p] < heap[c] ){
				
				swap(heap[c],heap[p]);
				p = c ;
				c = 2 * c;
			}
			else
				break;
			
		}
		
	}
	
	fprintf(g,"%lld\n",smax);
	
	fclose(f);
	fclose(g);
	return 0;
}