Cod sursa(job #437574)

Utilizator mataevsMatei Chiperi mataevs Data 9 aprilie 2010 22:14:04
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.72 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define NMAX 100001

typedef struct {
	unsigned int ht;
	unsigned int g;
	unsigned int ns;
}elem;

int comp(const void *a, const void *b){
	elem *p1 = (elem*)a;
	elem *p2 = (elem*)b;
	if (p1->ns < p2->ns)
		return 1;
	if (p1->ns > p2->ns)
		return -1;
	return 0;
}

void upHeap(elem *heap[], int m){
	elem* aux;
	if (m == 1)
		return;
	if (heap[m/2]->g < heap[m]->g){
		aux = heap[m/2];
		heap[m/2] = heap[m];
		heap[m] = aux;
		upHeap(heap, m/2);
	}
}

void eliminaHeap(elem *heap[], int* size){
	elem *aux;
	int i,next;
	heap[1] = heap[*size];
	next = 1;
	(*size)--;
	
	do{
		i = next;
		if (2*i <= *size){
			if (heap[i]->g < heap[2*i]->g)
				next = 2*i;
			else
				next = i;
		}
		if (2*i+1 <= *size)
			if (heap[next]->g < heap[2*i+1]->g)
				next = 2*i+1;
		if (next != i){
			aux = heap[next];
			heap[next] = heap[i];
			heap[i] = aux;
		}
	}
	while (next != i);
}

int main(){
	unsigned int n,h,u;
	int i, j;
	elem *gutui, *p;
	elem *heap[NMAX];
	int size;
	int g = 0;
	FILE *fin = fopen("gutui.in", "r");
	fscanf(fin,"%d %d %d",&n,&h,&u);
	gutui = (elem*)malloc(n * sizeof(elem));
	for (p = gutui, i = 0; i < n; i++, p++){
		fscanf(fin,"%d %d", &(p->ht), &(p->g));
		p->ns = (h - p->ht) / u + 1;
	}
	fclose(fin);
	
	qsort(gutui, n, sizeof(elem),comp);
	for (p = gutui, j = 0, i = gutui->ns; i >= 1; i--){
		while (p->ns == i && j < n){
			size++;
			heap[size] = p;
			upHeap(heap, size);
			p++;
			j++;
		}
		if (size != 0){
			g += heap[1]->g;
			eliminaHeap(heap,&size);
		}
	}
	
	FILE *fout = fopen("gutui.out", "w");
	fprintf(fout, "%d\n", g);
	fclose(fout);
	return 0;
}