Cod sursa(job #144050)

Utilizator tvladTataranu Vlad tvlad Data 27 februarie 2008 09:41:39
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

struct oaie { int w,d; };

const int N = 100000;

int n;
oaie o[N];

bool sort_cmp ( const oaie &a, const oaie &b ) { return (a.d > b.d); };
class set_cmp {
public:
	bool operator() ( const oaie &a, const oaie &b ) { return (a.w > b.w); };
};

template <class T, class cmp> class heap {
	T* v;
	int n;
	int alloc;
	void extend() {
		int new_alloc = alloc * 2;
		T* new_v = (T*)malloc(sizeof(T)*alloc);
		memcpy(new_v,v,n*sizeof(T));
		free(v);
		v = new_v;
		alloc = new_alloc;
	};
public:
	heap() {
		alloc = 2;
		v = (T*)malloc(sizeof(T)*2);
	};
	~heap() {};
	void insert ( T x ) {
		if ( n == alloc ) extend();
		++n;
		v[n] = x;
		for (int c = n; c > 0 && v[c/2] < v[c]; ) {
			T tmp = v[c];
			v[c] = v[c/2];
			v[c/2] = tmp;
			c /= 2;
		}
	};
	T* top() { return v; };
	void pop() {
		T tmp = v[0];
		v[0] = v[n];
		v[n] = tmp;
		--n;
		for (int c = 0; ; ) {
			if (cmp(v[c],v[c*2])) {
				if (!cmp(v[c*2],v[c*2+1])) {
					tmp = v[c];
					v[c] = v[c*2];
					v[c*2] = tmp;
				} else {
					tmp = v[c];
					v[c] = v[c*2+1];
					v[c*2+1] = tmp;
				}
			} else
			if (!cmp(v[c],v[c*2+1])) {
				tmp = v[c];
				v[c] = v[c*2+1];
				v[c*2+1] = tmp;
			} else {
				break;
			}
		}
	};
};

int main() {
	freopen("lupu.in","rt",stdin);
	freopen("lupu.out","wt",stdout);
	int x, dp;
	scanf("%d %d %d",&n,&x,&dp);
	for (int i = 0; i < n; ++i) {
		scanf("%d %d",&o[i].d,&o[i].w);
		o[i].d = ((x-o[i].d)/dp)+1;
	}
	sort(o,o+n,sort_cmp);
	long long r = 0;
	heap<oaie,set_cmp> heap;
	for (int t = o[0].d, i = 0; t; --t) {
		for (; i < n && o[i].d == t; heap.insert(o[i]), ++i);
		if (!heap.empty()) {
			r += (long long)heap.top()->w;
			heap.pop();
		}
	}
	printf("%lld\n",r);
	return 0;
}