Cod sursa(job #73122)

Utilizator tvladTataranu Vlad tvlad Data 16 iulie 2007 21:03:03
Problema Lupul Urias si Rau Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 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;
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) {
			tip temp = v[cur/2];
			v[cur/2] = v[cur];
			v[cur] = temp;
		}
	};
	tip& front() { return v[0]; };
	void pop() {
		int cur = v.size() - 1;
		tip temp = v[0];
		v[0] = v[cur];
		v[cur] = temp;
		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]) {
					temp = v[cur];
					v[cur] = v[2*cur];
					v[2*cur] = temp;
					cur = 2*cur;
				} else {
					temp = v[cur];
					v[cur] = v[2*cur+1];
					v[2*cur+1] = temp;
					cur = 2*cur+1;
				}
			} else
			if (st) {
				temp = v[cur];
				v[cur] = v[2*cur];
				v[2*cur] = temp;
				cur = 2*cur;
			} else
			if (dr) {
				temp = v[cur];
				v[cur] = v[2*cur+1];
				v[2*cur+1] = temp;
				cur = 2*cur+1;
			} else {
				break;
			}
		}
	};
};

const int N = 100000;

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

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

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

	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,comp_oaie_desc_dist);
	
	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;
}