Pagini recente » Cod sursa (job #499838) | Monitorul de evaluare | Cod sursa (job #231333) | Profil Pop_Marian | Cod sursa (job #441646)
Cod sursa(job #441646)
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MINF INT_MIN
#define PINF INT_MAX
#define IN "gutui.in"
#define OUT "gutui.out"
#define Left(i) ((i)<<1)
#define Right(i) (((i)<<1) + 1)
#define Father(i) ((i)>>1)
typedef struct
{
int h;
int w;
} GUTUIE;
typedef struct
{
int head; //unde adaug urmatorul element in heap
int dim;
GUTUIE *values;
} HEAP, *PHEAP;
PHEAP CreateV (int dim)
{
int i;
PHEAP H = (PHEAP) calloc (1, sizeof(HEAP));
H->dim = dim;
H->head = 1;
H->values = (GUTUIE*)calloc(dim+1, sizeof(GUTUIE));
for (i = 1 ; i <= H->dim ; ++i)
{
H->values[i].h = MINF;
H->values[i].w = PINF;
}
return H;
}
void FreeV (PHEAP H)
{
free (H->values);
free (H);
}
void print_g(GUTUIE G)
{
printf("Gutuie :\tinaltime: %d\t greutate: %d\n", G.h, G.w);
printf("\n");
}
void Print (PHEAP H)
{
int i;
for (i = 1 ; i <= H->dim ; ++i)
print_g (H->values[i]);
printf("\n");
}
void RHeap (PHEAP H, int poz)
{
int left = Left(poz);
int right = Right(poz);
int minim = PINF;
if (left <= H->head-1 && ((H->values[left]).w < (H->values[poz]).w) )
minim = left;
else
minim = poz;
if (right <= H->head-1 && ((H->values[right]).w < (H->values[minim]).w) )
minim = right;
if (minim != poz)
{
GUTUIE *aux = (GUTUIE*)calloc (1, sizeof(GUTUIE));
*aux = H->values[poz];
H->values[poz] = H->values[minim];
H->values[minim] = *aux;
free(aux);
RHeap (H, minim);
}
}
void CreateH (PHEAP H)
{
int i;
for (i = H->dim/2 ; i >= 1; --i)
{
RHeap (H, i);
H->head++;
}
}
void ShiftUp (PHEAP H, int poz)
{
int father = Father (poz);
if (H->values[father].w > H->values[poz].w)
{
GUTUIE aux = H->values[poz];
H->values[poz] = H->values[father];
H->values[father] = aux;
if (father == 0)
return;
ShiftUp(H, father);
}
else
return;
}
int Add (PHEAP H, GUTUIE g)
{
if (H->head > H->dim+1)
return -1;
H->values[H->head] = g;
ShiftUp (H, H->head);
H->head++;
return 1;
}
GUTUIE ExtractMin (PHEAP H)
{
GUTUIE aux = H->values[1];
H->values[1] = H->values[H->head-1];
H->head--;
RHeap (H, 1);
return aux;
}
int compare (const void *a, const void *b)
{
return ((GUTUIE*)b)->h - ((GUTUIE*)a)->h;
}
unsigned long GetWeight (PHEAP H)
{
unsigned long G = 0;
GUTUIE *g = (GUTUIE*) calloc (1, sizeof(GUTUIE));
while (1)
{
*g = ExtractMin (H);
// printf("%d\t", g->w);
G += g->w;
if (H->head == 1)
break;
}
free(g);
return G;
}
int main (int argc, char **argv)
{
int N, H, U, i, j;
unsigned long G = 0;
GUTUIE *g;
FILE *fin = fopen (IN, "r");
FILE *fout = fopen (OUT, "w");
fscanf (fin, "%d%u%u", &N, &H, &U);
g = (GUTUIE*) calloc (N, sizeof(GUTUIE));
PHEAP Heap = CreateV (N+1);
for (i = 0; i < N; ++i)
fscanf(fin, "%d%d", &g[i].h, &g[i].w);
qsort (g, N, sizeof(GUTUIE), compare);
int cnt;
int prev = H/U+1, current = 0;
GUTUIE *aux = (GUTUIE*) calloc (1, sizeof(GUTUIE));
for (i = 0; i < N; ++i)
{
current = g[i].h/U + 1;
cnt = prev - current;
if (cnt > 1)
{
for (j = 0 ; j < cnt ; ++j)
{
if ( i+j >= N )
break;
Add (Heap, g[i+j]);
G += g[i+j].w;
}
i = i + cnt - 1;
prev = current;
continue;
}
if (current == prev)
{
if (g[i].h + i * U <= H)
{
Add (Heap, g[i]);
G += g[i].w;
}
else if (g[i].w > Heap->values[1].w)
{
*aux = ExtractMin (Heap);
Add (Heap, g[i]);
G += (g[i].w - aux->w);
}
}
else
{
Add (Heap, g[i]);
G += g[i].w;
}
prev = current;
}
free (aux);
G = GetWeight (Heap);
fprintf (fout, "%lu\n", G);
//printf ("%ld\n", G);
fclose(fin);
fclose(fout);
FreeV (Heap);
free (g);
return 0;
}