Cod sursa(job #440780)

Utilizator dragospDragos Pricope dragosp Data 12 aprilie 2010 15:26:51
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 2.22 kb
#include <stdio.h>
#include <stdlib.h>

int N, H, U;

typedef struct s {
	int h, m;
	} gutuie;

struct HeapStruct {
    int Capacity;
    int Size;
    gutuie* Elem;
};

typedef struct HeapStruct *Heap;

int compare (const void * a, const void * b) {
	if(((*(gutuie*)a).h) == ((*(gutuie*)b).h))
		return (((*(gutuie*)a).m) - ((*(gutuie*)b).m));
  	return ( ((*(gutuie*)b).h)/U - ((*(gutuie*)a).h)/U );
}

Heap initialize(int N) {
    Heap H;
    H = malloc(sizeof ( struct HeapStruct));
    H->Elem = malloc((N + 1) * sizeof (gutuie));
    H->Capacity = N;
    H->Size = 0;
    (H->Elem[0]).m = 32767;
    return H;
}

void insert(gutuie X, Heap H) {
    int i;
    for (i = ++H->Size; (H->Elem[ i / 2 ]).m < X.m; i /= 2)
        H->Elem[ i ] = H->Elem[ i / 2 ];
    H->Elem[ i ] = X;
}

gutuie findMax(Heap H) {
	return H->Elem[ 1 ];
}

gutuie deleteMax(Heap H) {
    int i, Child;
    gutuie MaxElement, LastElement;
	MaxElement = H->Elem[ 1 ];
	LastElement = H->Elem[ H->Size-- ];
	for (i = 1; i * 2 <= H->Size; i = Child) {
		Child = i * 2;
		if (Child != H->Size && (H->Elem[ Child + 1 ]).m > (H->Elem[ Child ]).m)
			Child++;
		if (LastElement.m < (H->Elem[ Child ]).m)
			H->Elem[ i ] = H->Elem[ Child ];
        else
			break;
	}
	H->Elem[ i ] = LastElement;
	return MaxElement;
}

int isEmpty(Heap H) {
    return H->Size == 0;
}

int max(int a, int b) {
	if(a>b)
		return a;
	return b;
}

int main() {
	FILE *fin = fopen("gutui.in","r");
	FILE *fout = fopen("gutui.out","w");
	fscanf(fin,"%d%d%d",&N,&H,&U);
	gutuie* gutui = (gutuie*) malloc(N*sizeof(gutuie));
	int i;
	for(i=0;i<N;i++)
		fscanf(fin,"%d%d",&gutui[i].h,&gutui[i].m);
	int quantity = 0;
	if(U==0) { 
		for(i=0;i<N;i++)
			quantity+=gutui[i].m;
		fprintf(fout,"%d\n",quantity);
		return 0;
	}	
	qsort (gutui, N, sizeof(gutuie), compare);

	
	int dif = U - H % U, top;
  	if (dif == U) 
  		dif = 0;
  	top = dif - U;
	Heap heap = initialize(N);
	int n = N-1;
	while((n>=0 || !isEmpty(heap)) && top <= H) {
		if(!isEmpty(heap)) {
			quantity += (deleteMax(heap)).m;
      		top += U;
		}
		else {
			top += U * max(1, (gutui[n].h - top) / U);
		}
		while (n>=0 && gutui[n].h <= top) {
      		insert(gutui[n],heap);
      		n--;
    	}
	}
	fprintf(fout,"%d\n",quantity);
	fclose(fout);
	return 0;
}