#include <stdio.h>
#include <stdlib.h>
typedef struct heap
{
void **elem;
int dimensiune/*dimensiune heap*/,capacitate/*capacitatea maxima a vectorului*/;
} Heap;
Heap createHeap ()
{
Heap H;
H.elem = (void**)calloc(1, sizeof(void*));
H.capacitate = 1;
H.dimensiune = 0;
return H;
}
int dimHeap (Heap H)
{
return H.dimensiune;
}
int capacitHeap (Heap H)
{
return H.capacitate;
}
int parinte (Heap H, int poz)
{
int p;
p = (poz - 1)/2;
if (p < 0)
return -1;
return p;
}
int stHeap (Heap H, int poz)
{
int p;
p = 2*poz + 1;
if (p >= dimHeap(H))
return -1;
return p;
}
int drHeap (Heap H, int poz)
{
int p;
p = 2*poz + 2;
if (p >= dimHeap(H))
return -1;
return p;
}
void * elem_atHeap (Heap H, int poz)
{
if (poz < 0 || poz >= dimHeap(H))
return NULL;
return H.elem[poz];
}
void exchangeHeap (Heap *H, int p1, int p2)
{
if (p1 < 0 || p1 >= dimHeap(*H))
return;
if (p2 < 0 || p2 >= dimHeap(*H))
return;
void *aux;
aux = elem_atHeap(*H, p1);
H->elem[p1] = elem_atHeap(*H, p2);
H->elem[p2] = aux;
}
void urcareHeap (Heap *H, int p, int (*f)())
{
while (parinte(*H,p) >= 0 && f(elem_atHeap(*H, p), elem_atHeap(*H, parinte(*H, p))) < 0)
{
exchangeHeap(H,p,parinte(*H,p));
p = parinte(*H, p);
}
}
void * min_nodHeap (Heap H, int poz, int (*f)())
{
void *min = elem_atHeap(H,poz);
if (elem_atHeap(H, stHeap(H, poz)) != NULL)
if (f(min, elem_atHeap(H, stHeap(H, poz))) > 0)
min = elem_atHeap(H, stHeap(H, poz));
if (elem_atHeap(H, drHeap(H, poz)) != NULL)
if (f(min, elem_atHeap(H, drHeap(H, poz))) > 0)
min = elem_atHeap(H, drHeap(H, poz));
return min;
}
void coboaraHeap (Heap *H, int p, int (*f)())
{
while (1)
{
void *min = min_nodHeap(*H, p, f);
if (min == elem_atHeap(*H, p))
break;
int pe = 0;
if (min == elem_atHeap(*H, stHeap(*H, p)))
pe = stHeap(*H, p);
if (min == elem_atHeap(*H, drHeap(*H, p)))
pe = drHeap(*H, p);
exchangeHeap(H, p, pe);
p = pe;
}
}
void insertHeap (Heap *H, void *x, int (*f)())
{
H->dimensiune++;
if (H->dimensiune == H->capacitate)
{
H->elem = (void**)realloc(H->elem, (2*(H->capacitate) + 1)*sizeof(void*));
H->capacitate = 2*(H->capacitate) + 1;
}
H->elem[dimHeap(*H)-1] = x;
int p = dimHeap(*H) - 1;
urcareHeap(H, p, f);
}
void * extrageHeap (Heap *H, int (*f)())
{
if (dimHeap(*H) < 1)
return NULL;
void *x;
x = elem_atHeap(*H,0);
exchangeHeap(H, 0, dimHeap(*H) - 1);
H->dimensiune--;
coboaraHeap(H, 0, f);
return x;
}
typedef struct obiecte {
long inaltime;
long greutate;
long round;
} Obiecte;
int comparator (const void *O1, const void *O2)
{
Obiecte *o1, *o2;
o1 = (Obiecte *)O1;
o2 = (Obiecte *)O2;
if (o1->round < o2->round)
return -1;
if (o1->round == o2->round) {
if (o1->greutate < o2->greutate)
return 1;
else
if (o1->greutate == o2->greutate)
return 0;
else
return -1;
}
return 1;
}
int compHeap (void *a, void *b)
{
Obiecte *o1, *o2;
o1 = (Obiecte *)a;
o2 = (Obiecte *)b;
if (o1->greutate < o2->greutate)
return -1;
else
if (o1->greutate == o2->greutate)
return 0;
return 1;
}
int main()
{
FILE *f = fopen("gutui.in", "r");
FILE *g = fopen("gutui.out", "w");
long N, H, U, G = 0, i, *obj;
Obiecte *gutui;
/* Numărul de gutui */
fscanf(f, "%ld", &N);
gutui = calloc(N, sizeof(Obiecte));
obj = calloc(N + 1, sizeof(long));
/* Înălțimea maximă la care poate ajunge Gigel */
fscanf(f, "%ld", &H);
/* Cu cât se ridică crengile */
fscanf(f, "%ld", &U);
for (i = 0; i < N; i++) {
fscanf(f, "%ld", &gutui[i].inaltime);
fscanf(f, "%ld", &gutui[i].greutate);
gutui[i].round = (H - gutui[i].inaltime) / U + 1;
}
qsort(gutui, N, sizeof(Obiecte), comparator);
long k = 0;
Heap heap;
heap = createHeap();
for (i = 0; i < N; i++) {
if (k < gutui[i].round) {
k++;
G += gutui[i].greutate;
gutui[i].round = k;
insertHeap(&heap, &gutui[i], compHeap);
}
else {
/* caut în heap un element cu greutate mai mică */
Obiecte *gutuie;
gutuie = (Obiecte *)elem_atHeap(heap, 0); /* greutatea minimă din heap */
if (gutuie->greutate < gutui[i].greutate) {
gutui[i].round = gutuie->round;
G -= gutuie->greutate;
g += gutui[i].greutate;
gutuie = extrageHeap (&heap, compHeap);
insertHeap(&heap, &gutui[i], compHeap);
}
}
}
fprintf(g, "%ld", G);
/* for (i = 0; i < N; i++)*/
/* fprintf(g, "%ld %ld %ld\n" ,gutui[i].inaltime, gutui[i].greutate, gutui[i].round); */
return 0;
}