Pagini recente » Cod sursa (job #2901465) | Cod sursa (job #1281606) | Cod sursa (job #1076692) | Cod sursa (job #928802) | Cod sursa (job #438148)
Cod sursa(job #438148)
/*
Barca Cristian Mihai - 322CB
tema1 PA - prob2: Gutui
*/
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001
typedef struct heap {
int v, ind;
} THEAP;
typedef struct gutuie {
int h, g, tmin;
} TGUTUIE;
THEAP h[NMAX + 1];
TGUTUIE gutui[NMAX + 1];
int l_heap;
int T, N, H, U;
int comp (const void *a, const void *b) {
TGUTUIE x, y;
x = *(TGUTUIE *)a;
y = *(TGUTUIE *)b;
return (x.tmin - y.tmin);
}
void insert_heap(int timp, int ap) {
THEAP val;
int vf, baza;
l_heap++;
h[l_heap].ind = timp;
h[l_heap].v = ap;
for (vf = l_heap, val = h[l_heap], baza = l_heap/2; baza > 0; baza /= 2) {
if (val.v < h[baza].v) {
h[vf] = h[baza];
vf = baza;
}
else break;
}
h[vf] = val;
}
void pop_heap(int *timp) {
THEAP val;
int vf, baza;
*timp = h[1].ind;
h[1] = h[l_heap];
l_heap--;
for (vf = 1, val = h[1], baza = 2; baza <= l_heap; baza *= 2) {
if (baza < l_heap && h[baza].v > h[baza + 1].v) baza++;
if (val.v > h[baza].v) {
h[vf] = h[baza];
vf = baza;
}
else break;
}
h[vf] = val;
}
int main() {
int last, i, j, k, timp;
long long totG = 0;
freopen("gutui.in", "rt", stdin);
freopen("gutui.out", "wt", stdout);
scanf("%d %d %d", &N, &H, &U);
for (i = 1; i <= N; i++) {
scanf("%d %d", &gutui[i].h, &gutui[i].g);
if (H < gutui[i].h) gutui[i].tmin = 0;
else gutui[i].tmin = (H - gutui[i].h)/U + 1;
}
qsort(gutui + 1, N, sizeof(TGUTUIE), comp);
for (i = 1; i <= N && !gutui[i].tmin; i++);
last = 1;
for (; i <= N; i = j) {
for (j = i; j <= N && gutui[j].tmin == gutui[i].tmin; j++);
for (; last <= gutui[i].tmin; last++) insert_heap(last, 0);
for (k = i; k < j; k++)
if (h[1].v < gutui[k].g) {
pop_heap(&timp);
insert_heap(timp, gutui[k].g);
}
}
for (i = 1; i <= l_heap; i++) {
printf("%d %d\n", h[i].ind, h[i].v);
totG += h[i].v;
}
printf("%lld\n", totG);
return 0;
}