Cod sursa(job #534782)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 16 februarie 2011 10:54:10
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<stdio.h>
#include<algorithm>
#define Nmax 100010
using namespace std;

struct oi { int D ; int val ; } v[Nmax];

int cmp( oi a, oi b ) 
{
	return a.D < b.D ; 
}

int h[Nmax],poz[Nmax];
int i,n,L,l,x,K,step,ld;
long long sol ;

void swap ( int i,  int j )
{
	poz[h[i]] = j ;
	poz[h[j]] = i ; 
	
	int aux = h[i] ; h[i] = h[j] ; h[j] = aux ;
}

int pozmax ( int i ) 
{
	int j = (i<<1) ;
	
	if( j < L ) 
		if( v[h[j+1]].val > v[h[j]].val ) return j + 1 ;
	return j ;
}

void down ( int i ) 
{
	if ( i <= (L>>1) ) 
	{
		int k = pozmax(i);
		if( v[h[k]].val > v[h[i]].val ) 
		{
			swap(i,k);
			down(k);
		}
	}
}

void up ( int  i ) 
{
	int j = (i>>1) ; 
	
	if( i > 1 )
	{
		if( v[h[i]].val > v[h[j]].val )
		{
			swap(i,j);
			up(j);
		}
	}
}

void push ( int x )
{
	h[++L] = x ;
	poz[x] = L ;
	up(L);
}

void pop ( int p )
{
	swap(p,L);
	poz[h[L]] = 0 ; 
	h[L] = 0 ; L--;
	down(p);
}

int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	
	scanf("%d %d %d",&n,&x,&l);
	
	if( !l ) 
	{
		for( i = 1 ; i <= n ; i++ )
			scanf("%d %d",&v[i].D,&v[i].val);
		
		if( v[i].D <= x ) sol += (long long)v[i].val ;
		printf("%lld",sol);
		return 0;
	}
	
	for( i = 1 ; i <= n ; i++ )
	{
		K++;
		scanf("%d %d",&v[K].D,&v[K].val) ;
		
		if( v[i].D > x ) { K--; continue ; }
		
		v[K].D = 1 + ( x - v[K].D ) / l ;
		if( v[K].D > ld ) ld = v[K].D ;
	}
	
	sort(v+1,v+K+1,cmp);
	
	i = n ;
	for( step = ld ; step ; step-- )
	{
		for( ; v[i].D == step && i ; i-- )
			push(i);
		
		if( !L ) continue ;
		
		sol += (long long)v[h[1]].val;
		pop(1);
		
		
	}
	
	printf("%lld",sol);
	
	return 0 ; 
}