Pagini recente » Cod sursa (job #2559086) | Cod sursa (job #419618) | Cod sursa (job #1023726) | Cod sursa (job #1209147) | Cod sursa (job #1981382)
#include <cstdio>
#include <algorithm>
const int MAX_N = 100000;
struct Sheep {
int lana, dist;
} v[MAX_N];
bool cmp(Sheep a, Sheep b) {
return a.dist > b.dist;
}
int heap[1+MAX_N], size;
inline void swap(int &a, int &b) {
int aux = a;
a = b;
b = aux;
}
inline void upheap(int p) {
while(p > 1) {
if(heap[p] < heap[p / 2])
swap(heap[p], heap[p / 2]);
p = p / 2;
}
}
inline void downheap(int p) {
int poz = p;
while(p <= size) {
if(2 * p <= size && heap[2 * p] < heap[poz])
poz = 2 * p;
if(2 * p + 1 <= size && heap[2 * p + 1] < heap[poz])
poz = 2 * p + 1;
if(poz == p)
p = size + 1;
else {
swap(heap[p], heap[poz]);
p = poz;
}
}
}
inline void add(int x) {
++size;
heap[size] = x;
upheap(size);
}
int main() {
int n, dist, maxdist, selectate = 0;
long long suma = 0LL;
FILE *fin = fopen("lupu.in", "r");
fscanf(fin, "%d%d%d", &n, &maxdist, &dist);
for(int i = 0; i < n; ++i)
fscanf(fin, "%d%d", &v[i].dist, &v[i].lana);
fclose(fin);
std::sort(v, v + n, cmp);
for(int i = 0; i < n; ++i) {
if((long long)dist * selectate + v[i].dist <= maxdist) {
add(v[i].lana);
++selectate;
} else if(v[i].lana >= heap[1]) {
heap[1] = v[i].lana;
downheap(1);
}
}
for(int i = 1; i <= size; ++i)
suma = suma + heap[i];
FILE *fout = fopen("lupu.out", "w");
fprintf(fout, "%lld", suma);
fclose(fout);
return 0;
}