Cod sursa(job #5704)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 13 ianuarie 2007 21:01:34
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define FIN "lupu.in"
#define FOUT "lupu.out"
#define MAX 100050
#define pozMin 100040

struct oaie {
	long l, d;
};
long X,L,N, ans;
long T[MAX], O[MAX];
oaie A[MAX];

class heap {
	private:
	oaie H[MAX];
	long Nh;


	inline long t(long x) {
		return (x-1) / 2;
	}
	inline long fs(long x) {
		return (x*2) + 1;
	}
	inline long fd(long x) {
		return (x*2) + 2;
	}
	inline void swap(long p1, long p2) {
		oaie aux = H[p1]; H[p1] = H[p2]; H[p2] = aux;
	}

	public:
	heap() {
		Nh=0;
		H[pozMin].l = -1;
	}
	bool empty() {
		return (Nh==0);
	}
	bool comp(long offset) {
		return H[0].d + offset > X;
	}
	void push(long l, long d) {
		oaie temp; long i;

		temp.l = l; temp.d = d;
		H[Nh++] = temp;
		// heapUp
		for (i=Nh-1; i &&  H[t(i)].l < H[i].l; i=t(i)) 	
			swap(i, t(i));
	}
	oaie pop() {
		oaie temp = H[0];
		long i, p, f;

		// heapDown
		H[0] = H[--Nh];
		for ( i=0; fs(i)<Nh && 
				H[(
					p = ( H[fs(i)].l>H[ f = (fd(i)<=Nh ? fd(i) : pozMin) ].l || (H[fs(i)].l == H[f].l && H[fs(i)].d > H[f].d) )
						? fs(i) : fd(i)
				  )
				 ].l > H[i].l ; 
				i=p ) 
			swap(p, i);
		return temp;
	}
} H;

void read_data() {
	long i;
	
	freopen(FIN, "r", stdin);
	scanf("%ld %ld %ld", &N, &X, &L);
	for (i=0; i<N; ++i) {
		scanf("%ld %ld", &A[i].d, &A[i].l);
		O[i]=i;
		for (T[i] = 0;  T[i]*L+A[i].d<=X ; ++ T[i]);
	}
	fclose(stdout);
}

bool comp(const long &x, const long &y) {
	return (T[x]>T[y]);
}

void solve() {
	long i = 0, pos, ok;
	oaie temp;
	sort(O, O+N, comp);
	for (pos=N-1; ! T[O[pos]]; --pos);

	for (i=0; pos>=0 || !H.comp(L*i); i++) {
		for (ok = T[O[pos]]; T[O[pos]] == ok; --pos) 
			H.push(A[O[pos]].l, A[O[pos]].d);
//		pos--;

		while ( H.comp(L*i) && !H.empty() ) 
			H.pop();

		if ( !H.empty() ) {
			temp = H.pop();
			ans += temp.l;
		}
	}
}

void write_answer() {
	freopen(FOUT, "w", stdout);
	printf("%ld\n", ans);
	fclose(stdout);
}

int main() {
	read_data();
	solve();
	write_answer();
	return 0;
}