Cod sursa(job #147522)

Utilizator plastikDan George Filimon plastik Data 3 martie 2008 09:24:45
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
// Lupu Urias si Rau
// http://infoarena.ro/problema/lupu

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

#define time first
#define wool second
#define MAX_N 100005

int Heap[MAX_N];
pair<int, int> Sheep[MAX_N];
int n, x, l;

bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.time > b.time)
		return true;
	else
		return false;
}

void heapify(int i) {
	int aux, left = 2 * i, right = 2 * i + 1;

	if (left <= Heap[0] && Heap[i] < Heap[left]) {
		aux = Heap[i];
		Heap[i] = Heap[left];
		Heap[left] = aux;
		heapify(left);
		return;
	}

	if (right <= Heap[0] && Heap[i] < Heap[right]) {
		aux = Heap[i];
		Heap[i] = Heap[right];
		Heap[right] = aux;
	}
}

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

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

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

	return 0;
}