Pagini recente » Cod sursa (job #3179881) | Cod sursa (job #470495) | Cod sursa (job #1856672) | Cod sursa (job #2967491) | Cod sursa (job #147690)
Cod sursa(job #147690)
// 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;
}