Cod sursa(job #147690)

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

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

#define MAX_N 100005

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) {

		//intf("Sheep:\n");
		for (; i < n && Sheep[i].time == t; ++ i) {
			//printf("%d ", Sheep[i].wool);
			insertHeap(Sheep[i].wool);
		}

		/*printf("\nT:%d\n", t);
		for (j = 1; j <= Heap[0]; ++ j)
			printf("%d ", Heap[j]);
		printf("\n");*/

		ans += popHeap();
	}

	/*for (i = 0; i < n; ++ i)
		printf("%d %d\n", Sheep[i].time, Sheep[i].wool);

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

	return 0;
}