Cod sursa(job #5697)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 13 ianuarie 2007 20:13:15
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <cstdio>
#define FIN "lupu.in"
#define FOUT "lupu.out"
#define MAX 100050
#define pozMin 100040

struct oaie {
	long l, d;
};
long X,L,N, ans;

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) {
		long l,d;
		scanf("%ld %ld", &d, &l);
		H.push(l,d);
	}
	fclose(stdout);
}

void solve() {
	long i = 0;
	oaie temp;
	
	for (i=0; !H.empty(); i++) {
		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;
}