Cod sursa(job #147697)

Utilizator plastikDan George Filimon plastik Data 3 martie 2008 13:26:14
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
// Lupu Urias si Rau
// http://infoarena.ro/problema/lupu

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_N 1000203

struct sheep {
	int wool, time;
};

int Heap[MAX_N];
sheep Sheep[MAX_N];
int n, x, l;


bool compare(sheep a, sheep b) {
	if (a.time > b.time)
		return true;
	return false;
}

void heapify(int i) {
	int aux, left = 2 * i, right = 2 * i + 1;
	int lh = 0, rh = 0;
	if (left <= Heap[0])
		lh = Heap[left];
	if (right <= Heap[0])
		rh = Heap[right];

	if (lh <= rh)
		if (rh > Heap[i]) {
			aux = Heap[i];
			Heap[i] = Heap[right];
			Heap[right] = aux;
			heapify(right);
			return;
		} else ;
	else
		if (lh > Heap[i]) {
			aux = Heap[i];
			Heap[i] = Heap[left];
			Heap[left] = aux;
			heapify(left);
		}
}

int popHeap() {
	int aux = Heap[Heap[0]], ret = Heap[1];
	Heap[Heap[0]] = Heap[1];
	Heap[1] = aux;
	-- Heap[0];
	heapify(1);
	return ret;
}

void insertHeap(int key) {
	Heap[++ Heap[0]] = key;
	int aux, i = Heap[0], parent = i / 2;
	for (; parent != 0 && Heap[parent] < Heap[i]; i = parent, parent /= 2) {
		aux = Heap[i];
		Heap[i] = Heap[parent];
		Heap[parent] = aux;
	}
}

int main() {
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out", "w", stdout);

	scanf("%d %d %d", &n, &x, &l);
	int i, j, w, d;
	for (i = 0; i < n; ++ i) {
		scanf("%d %d", &d, &w);
		Sheep[i].time = (x - d) / l + 1;
		Sheep[i].wool = w;
	}

	sort(Sheep, Sheep + n, compare);
	
	int t;
	long long ans = 0;
	Heap[0] = 0;
	for (t = Sheep[0].time, i = 0; t > 0; -- t) {

		for (; i < n && Sheep[i].time == t; ++ i)
				insertHeap(Sheep[i].wool);
		ans += popHeap();

	}

	printf("%lld\n", ans);

	return 0;
}