Cod sursa(job #436800)

Utilizator violeta.marinVioleta Marin violeta.marin Data 8 aprilie 2010 23:20:42
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.87 kb
#include <stdio.h>
#include <stdlib.h>

struct gut{
	unsigned int level;	
	unsigned int weight;
	};

struct gut *gutui;

int compare (const void * a, const void * b)
{
	if ((*(struct gut*)a).level == (*(struct gut*)b).level)	
		return -((*(struct gut*)a).weight - (*(struct gut*)b).weight); 
	 return ((*(struct gut*)a).level - (*(struct gut*)b).level); 	
}

unsigned int parent(unsigned int i){
	if (i % 2 == 0) return (i/2 - 1);
		else return i/2;
}
void insert(unsigned int w, unsigned int *heap, unsigned int pos){
heap[pos] = w;
unsigned int aux;
while ((pos > 0) && (heap[pos] < heap[parent(pos)])) {
					aux = heap[parent(pos)];
					heap[parent(pos)] = heap[pos];
					heap[pos] = aux;
					pos = parent(pos);
					}  
}

void minheapify(unsigned int *heap, unsigned int i, unsigned int length){

unsigned int l = 0, r = 0, least, aux;
if ((2 * i + 1) < length) l = 2 * i + 1;
if ((2 * i + 2) < length) r = 2 * i + 2;
if ((l == 0) || (r == 0)) return;
	else
	if ((l != 0) && (r == 0))
		{
		if (heap[l] < heap[i]) {
					aux = heap[i];
					heap[i] = heap[l];
					heap[l] = aux;
					minheapify(heap, l, length);
					}
				else return;
		}
	 else
		{
		if (heap[l] > heap[r]) least = r;
			else least = l;
		if (heap[i] > heap[least]) {
					//printf("!\n");
					   aux = heap[i];
					  heap[i] = heap[least];
					  heap[least] = aux;
					  minheapify(heap, least, length);	
					   }
		else return;	 	
 } 		}
int main(){
	unsigned int i, j, k, t;
	unsigned int h,u,n;	
	unsigned int level,no_levels, min_level = 0xffffffff;
	unsigned int *schedule;
	unsigned int max = 0;
	
	FILE *f = fopen("gutui4.in","r");
	fscanf(f, "%u", &n);
	fscanf(f, "%u", &h);
	fscanf(f, "%u", &u);
	
	
	/*
	printf("n = %u h = %u u = %u\n", n ,h,u);
	printf("%u\n", h/u);
	*/
	gutui = (struct gut *)malloc(n * sizeof(struct gut));
	
	for (i = 0; i < n; i++)
		{
		fscanf(f, "%u", &level);
		fscanf(f, "%u", &gutui[i].weight);
		gutui[i].level = (h - level)/u + 1 ;
		if (min_level > level) min_level = level;
		}
	fclose(f);

	qsort(gutui, n, sizeof(struct gut), compare);
	
	
	/*for (i = 0; i < n; i++)
		{
		printf("%u ", gutui[i].weight);
		printf("%u \n", gutui[i].level);
		}
	printf("\n");*/
	
	
	no_levels = (h - min_level)/u + 1;
	unsigned int * heap = (unsigned int *)calloc(no_levels,sizeof(unsigned int));
	for (i = 0; i < no_levels; i++)
		heap[i] = 0xffffffff;
	level = 0; k = 0; j = 0, t = 0; 	

	for (i = 0; i < n; i++){
		if (gutui[i].level > level) {
						level = gutui[i].level;
						k = 1;
						if (t < level) {
								t = t + 1;
								insert(gutui[i].weight, heap, level - 1);
								max = max + gutui[i].weight; 
								   }
							else
							  {
							if (heap[0] < gutui[i].weight) {
											max = max - heap[0] + gutui[i].weight;	
											heap[0] = gutui[i].weight;
											minheapify(heap, 0, level);
											}
							  }
						}
					else
					{
					k = k + 1;
					if (k <= gutui[i].level)
						if (t < level) {
								t = t + 1;
								insert(gutui[i].weight, heap, level - 1);
								max = max + gutui[i].weight; 
								   }
							else
							  {
							if (heap[0] < gutui[i].weight) {
											max = max - heap[0] + gutui[i].weight;	
											heap[0] = gutui[i].weight;
											minheapify(heap, 0, level);
											}
							  }
						
					}
		j++;
		}	 
								    
						
					    
		
	/*unsigned int * heap = (unsigned int *)calloc(9,sizeof(unsigned int));
	insert(36 , heap, 0);
	insert(100 , heap, 1);
	insert( 17, heap, 2);
	insert(25 , heap, 3);
	insert(19 , heap, 4);
	insert( 2, heap, 5);
	insert(7 , heap, 6);
	insert(3 , heap, 7);
	insert(1 , heap, 8);
	//insert( , heap, 0);	  
	for (i = 0; i < 9;i++)
		printf("%u ", heap[i]);
	printf("\n");
	heap[0] = 5;
	minheapify(heap, 0, 9);*/
	//for (i = 0; i < no_levels;i++)
	//	printf("%u ", heap[i]);
	//printf("\n");
	//printf("%u\n", max);
	f = fopen("gutui.out", "w");
	fprintf(f, "%u\n", max);
	fclose(f);
return 0;
}