Pagini recente » Cod sursa (job #164992) | Cod sursa (job #1157927) | Cod sursa (job #2230887) | Cod sursa (job #3197477) | Cod sursa (job #147522)
Cod sursa(job #147522)
// 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;
}