Pagini recente » Cod sursa (job #3200231) | Cod sursa (job #3124937) | Cod sursa (job #759064) | Cod sursa (job #1545609) | Cod sursa (job #2912621)
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100000
struct SheepData {
int d;
int a;
};
SheepData sheep[MAX_N];
//struct Node {
//vector<int> nodes;
//};
//vector<Node> heap;
struct Node {
int nodes[100];
};
Node heap[100];
bool cmp(SheepData a, SheepData b) { return a.d > b.d; }
static inline void swapVectElem(int depth, int indInRow) {
int aux = heap[depth].nodes[indInRow];
heap[depth].nodes[indInRow] = heap[depth - 1].nodes[indInRow / 2];
heap[depth - 1].nodes[indInRow / 2] = aux;
}
void updateHeap(int indInRow, int depth) {
if (depth <= 0)
return;
if (sheep[heap[depth].nodes[indInRow]].a < sheep[heap[depth - 1].nodes[indInRow / 2]].a)
swapVectElem(depth, indInRow);
updateHeap(indInRow / 2, depth - 1);
}
int main() {
FILE *fin, *fout;
int n, x, d;
int i, heapDepth, sum;
int nrInHeap, eated;
fin = fopen("lupu.in", "r");
fscanf(fin, "%d%d%d", &n, &x, &d);
//heap.resize(n + 1);
//for (i = 0; i < n; i++)
//heap[i].nodes.resize((1 << i) + 1);
for (i = 1; i <= n; i++)
fscanf(fin, "%d%d", &sheep[i].d, &sheep[i].a);
fclose(fin);
eated = 0;
nrInHeap = 0;
heapDepth = 0;
sheep[0].d = 0;
sheep[0].a = 0;
heap[0].nodes[0] = -1;
sort(sheep + 1, sheep + n + 1, cmp);
for (i = 1; i <= n; i++) {
if (heap[0].nodes[0] == -1) {
if (sheep[i].d <= x) {
heap[0].nodes[0] = i;
eated++;
heapDepth++;
}
} else {
if (sheep[heap[0].nodes[0]].a >= sheep[i].a) {
if (sheep[i].d + eated * d <= x) {
heap[heapDepth].nodes[nrInHeap] = i;
eated++;
nrInHeap++;
updateHeap(nrInHeap - 1, heapDepth);
}
} else if (sheep[heap[0].nodes[0]].a < sheep[i].a && sheep[i].d + eated * d > x) {
heap[0].nodes[0] = i;
for (int j = 0; j < nrInHeap; j++)
updateHeap(j, heapDepth);
} else if (sheep[heap[0].nodes[0]].a < sheep[i].a) {
if (sheep[i].d + eated * d <= x) {
heap[heapDepth].nodes[nrInHeap] = i;
eated++;
nrInHeap++;
updateHeap(nrInHeap - 1, heapDepth);
}
}
}
if (nrInHeap == (1 << heapDepth)) {
nrInHeap = 0;
heapDepth++;
}
//for (int depth = 0; depth < heapDepth + 1; depth++) {
//for (int pos = 0; pos < 1 << depth; pos++) {
//printf("%d ", heap[depth].nodes[pos]);
//}
//putc('\n', stdout);
//}
//putc('\n', stdout);
}
sum = 0;
for (int depth = 0; depth < heapDepth + 1; depth++) {
for (int pos = 0; pos < 1 << depth; pos++) {
//printf("%d ", heap[depth].nodes[pos]);
sum = sum + sheep[heap[depth].nodes[pos]].a;
}
//putc('\n', stdout);
}
//putc('\n', stdout);
fout = fopen("lupu.out", "w");
fprintf(fout, "%d\n", sum);
fclose(fout);
return 0;
}