Pagini recente » Cod sursa (job #578946) | Cod sursa (job #2217549) | Cod sursa (job #1963971) | Cod sursa (job #2027095) | Cod sursa (job #441543)
Cod sursa(job #441543)
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;
#define NMAX 100001
typedef struct {
int h, g, r;
} gutuie;
int compar(const void *a, const void *b) {
gutuie x, y;
x = *(gutuie *) a;
y = *(gutuie *) b;
return y.r - x.r;
}
int main() {
gutuie G[NMAX];
int N, HMAX, U, GMAX, i, T;
priority_queue<int> heap;
freopen("gutui.in", "rt", stdin);
freopen("gutui.out", "wt", stdout);
scanf("%d %d %d", &N, &HMAX, &U);
/* citirea datelor */
for (i = 0 ; i < N; i++) {
scanf("%d %d", &G[i].h, &G[i].g);
G[i].r = (HMAX - G[i].h) / U;
}
/* sortarea descrescatoare dupa timpii maximi de cules pentru fiecare gutuie */
qsort(G, N, sizeof(G[1]), compar);
/* greedy - la fiecare pas se introduc in heap greutatile gutuilor
cu timpul maxim egal cu timpul curent, si se extrage maximul */
for (i = 0, GMAX = 0, T = G[0].r; i < N && T >= 0; T--) {
while (G[i].r == T && i < N) {
heap.push(G[i].g);
i++;
}
if (!heap.empty()) {
GMAX += heap.top();
heap.pop();
}
}
/* daca s-au epuizat gutuile, dar timpul ne permite sa mai culegem,
atunci actualizam greutatea maxima */
while (T >=0 && !heap.empty()) {
GMAX += heap.top();
heap.pop();
T--;
}
printf("%d\n", GMAX);
fclose(stdin);
fclose(stdout);
return 0;
}