Pagini recente » Cod sursa (job #1876345) | Cod sursa (job #549334) | Cod sursa (job #1268504) | Cod sursa (job #1933358) | Cod sursa (job #1981378)
#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(selectate <= (maxdist - v[i].dist) / dist) {
add(v[i].lana);
suma = suma + v[i].lana;
++selectate;
} else if(v[i].lana > heap[1]) {
suma = suma - heap[1] + v[i].lana;
heap[1] = v[i].lana;
downheap(1);
}
}
FILE *fout = fopen("lupu.out", "w");
fprintf(fout, "%lld", suma);
fclose(fout);
return 0;
}