Cod sursa(job #73131)

Utilizator tvladTataranu Vlad tvlad Data 16 iulie 2007 22:08:33
Problema Lupul Urias si Rau Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;


struct oaie {
	int d,l;
	bool operator< ( oaie a ) { return l < a.l; };
	bool operator> ( oaie a ) { return l > a.l; };
};

template <class tip> class heap {
	vector<tip> v;
	void replace ( tip& a, tip& b ) { tip temp = a; a = b; b = temp; };
public:
	heap() {};
	~heap() {};
	void push ( tip x ) {
		v.push_back(x);
		for (int cur = v.size() - 1; cur > 0 && v[cur / 2] < v[cur]; cur /= 2) {
			replace(v[cur/2],v[cur]);
		}
	};
	tip& front() { return v[0]; };
	void pop() {
		int cur = v.size() - 1;
		replace(v[0],v[cur]);
		v.pop_back();
		cur = 0;
		for (;;) {
			bool st = (2*cur < v.size() && v[2*cur] > v[cur]);
			bool dr = (2*cur+1 < v.size() && v[2*cur+1] > v[cur]);
			if (st && dr) {
				if (v[2*cur] > v[2*cur+1])
					replace(v[cur],v[2*cur]); else 
					replace(v[cur],v[2*cur+1]);
			} else
			if (st) replace(v[cur],v[2*cur]); else
			if (dr) replace(v[cur],v[2*cur+1]); else
				break;
		}
	};
};

const int N = 100000;

int n,dm,dr;
oaie o[N];

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

int main() {
	freopen("lupu.in","rt",stdin);
	freopen("lupu.out","wt",stdout);
	freopen("lupu.err","wt",stderr);

	scanf("%d %d %d",&n,&dm,&dr);
	for (int i = 0; i<n; ++i) {
		scanf("%d %d",&o[i].d,&o[i].l);
		o[i].d = (dm - o[i].d)/dr + 1;
	}

	sort(o,o+n,compdd);
	
	heap<oaie> H;
	int r = 0;
	for (int i = 0; i<n; ++i) {
		H.push(o[i]);
		if(o[i].d != o[i+1].d) {
			r += (H.front()).l;
			H.pop();
		}
	}
	printf("%d\n",r);
	return 0;
}