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