Pagini recente » Cod sursa (job #2031216) | Cod sursa (job #1809677) | Cod sursa (job #1736937) | Cod sursa (job #448505) | Cod sursa (job #436524)
Cod sursa(job #436524)
#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 = MINF;
if (left <= H->dim && ((H->values[left]).w < (H->values[poz]).w) )
minim = left;
else
minim = poz;
if (right <= H->dim && ((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 == 1)
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];
H->head--;
RHeap (H, 1);
return aux;
}
int compare (const void *a, const void *b)
{
return ((GUTUIE*)b)->h - ((GUTUIE*)a)->h;
}
long GetWeight (PHEAP H)
{
long G = 0;
int cnt = 0;
GUTUIE *g = (GUTUIE*) calloc (1, sizeof(GUTUIE));
while (1)
//for (i = 0 ; i < H->dim ; ++i)
{
*g = ExtractMin (H);
cnt++;
if (g->w == PINF)
break;
G += g->w;
if (H->head == 1)
break;
}
free(g);
return G;
}
int main (int argc, char **argv)
{
int N, H, U, i, j, Hmin = PINF;
long G = 0;
GUTUIE *g;
FILE *fin = fopen (IN, "r");
FILE *fout = fopen (OUT, "w");
fscanf (fin, "%d%d%d", &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);
if ( Hmin > g[i].h )
Hmin = g[i].h;
}
qsort (g, N, sizeof(GUTUIE), compare);
int cnt = 0;
int prev = 0, current = 0;
GUTUIE *aux = (GUTUIE*) calloc (1, sizeof(GUTUIE));
for (i = 0; i < N; ++i)
{
current = g[i].h/U;
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;
cnt--;
}
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, "%ld\n", G);
fclose(fin);
fclose(fout);
FreeV (Heap);
free (g);
return 0;
}