Pagini recente » Cod sursa (job #2650803) | Cod sursa (job #519254) | Cod sursa (job #1406811) | Cod sursa (job #2250059) | Cod sursa (job #519248)
Cod sursa(job #519248)
/*
Barca Cristian Mihai - 322CB
tema1 PA - prob2: Gutui
*/
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001
// struct pt min-heap, dupa v
// .v -> valoare/greutate, .ind -> indicator/timp pt cules
typedef struct heap {
int v, ind;
} THEAP;
// struct pt gutui
typedef struct gutuie {
int h, g, tmin;
} TGUTUIE;
THEAP h[NMAX + 1];
TGUTUIE gutui[NMAX + 1];
int l_heap;
int T, N, H, U;
// fc de comp pt qsort, folosesc qsort pt sortarea cresc
// dupa timpul minim la care pot culege fiecare gutuie
// (cat de tarziu pot culege o gutuie)
int comp (const void *a, const void *b) {
TGUTUIE x, y;
x = *(TGUTUIE *)a;
y = *(TGUTUIE *)b;
return (x.tmin - y.tmin);
}
// inserare clasica in heap
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;
}
// extragere clasica din heap
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);
// citire date de intrare
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;
}
// aplicare qsort dupa tmin crescator
qsort(gutui + 1, N, sizeof(TGUTUIE), comp);
// eliminare gutui deja "expirate"
for (i = 1; i <= N && !gutui[i].tmin; i++);
// algoritm greedy + struct de date heap =>
// complexitate O(NlogN)
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);
}
}
// calcul grutate maxima totala
for (i = 1; i <= l_heap; i++) {
totG += h[i].v;
}
printf("%lld\n", totG);
return 0;
}