Cod sursa(job #985072)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 16 august 2013 13:41:39
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<fstream>
#include<queue>
#include<algorithm>


#define max_n 100010

using namespace std;

ifstream f("lupu.in");
ofstream g("lupu.out");

struct oaie{
	int d , a;
}V[max_n];

priority_queue< int , vector<int> , less<int> > H;


int n , x , l , d_max = -1;
int a , d , nr;
long long maxim;


bool cmp( oaie a , oaie b ){
	return a.d > b.d;
}


int main(){
	
	f>>n>>x>>l;
	
	for( int i = 1 ; i <= n ; i++ ){
		
		f>>d>>a;
		
		d = x - d;
		
		if( d > 0 ){
			V[++nr].d = d/l + 1 , V[nr].a = a;
			if( V[nr].d > d_max ) d_max = V[nr].d;
		}
		
	}
	
	sort( V + 1 , V + nr + 1 , cmp );
	
	int p = 1;
	
	for( int i = d_max ; i >= 1 ; i-- ){
		while( V[p].d == i ){
			H.push(V[p].a);
			p++;
		}
		
		if( H.empty() == 0 ){
			maxim += H.top();
			H.pop();
		}
		
	}
	
	g<<maxim<<"\n";
	
	return 0;
}