Pagini recente » Cod sursa (job #2676850) | Cod sursa (job #2307024) | Cod sursa (job #885036) | Cod sursa (job #1509075) | Cod sursa (job #2003142)
#include <cstdio>
#include <algorithm>
const int MAXN = 1e5;
struct S {
int b, d;
} v[MAXN];
int heap[MAXN + 1], len;
inline bool cmp(S a, S b) {
return a.d > b.d;
}
inline int father(int p) {
return (p - 1) / 2;
}
inline int leftson(int p) {
return 2 * p + 1;
}
inline int rightson(int p) {
return 2 * p + 2;
}
inline void swap(int &a, int &b) {
int aux = a;
a = b;
b = aux;
}
inline void up(int p) {
while (p > 0 && heap[p] < heap[father(p)]) {
swap(heap[p], heap[father(p)]);
p = father(p);
}
}
inline void down(int p) {
int x = p;
while (p <= len) {
if (leftson(p) <= len && heap[leftson(p)] < heap[x]) {
x = leftson(p);
}
if (rightson(p) <= len && heap[rightson(p)] < heap[x]) {
x = rightson(p);
}
if (x == p) {
p = len + 1;
} else {
swap(heap[p], heap[x]);
p = x;
}
}
}
inline void add(int p) {
++len;
heap[len] = p;
up(len);
}
int main() {
int n, cnt, maxd, dist;
long long ans;
FILE *f = fopen("lupu.in", "r");
fscanf(f, "%d%d%d", &n, &maxd, &dist);
for (int i = 0; i < n; ++i) {
fscanf(f, "%d%d", &v[i].d, &v[i].b);
}
fclose(f);
std::sort(v, v + n, cmp);
cnt = 0;
for (int i = 0; i < n; ++i) {
if (1LL * dist * cnt + v[i].d <= maxd) {
add(v[i].b);
++cnt;
} else if (heap[0] <= v[i].b) {
heap[0] = v[i].b;
down(0);
}
}
ans = 0LL;
for (int i = 0; i < len; ++i) {
ans += heap[i];
}
f = fopen("lupu.out", "w");
fprintf(f, "%lld\n", ans);
fclose(f);
return 0;
}