Cod sursa(job #437112)

Utilizator angel_pacPetre Andreea Cristina angel_pac Data 9 aprilie 2010 13:06:26
Problema Gutui Scor 40
Compilator c Status done
Runda teme_upb Marime 1.66 kb
#include <stdio.h>
#include <stdlib.h>
//structura gutuie :P
typedef struct gutui{
	int g, h, l;
}gutui_t;
 
//partitionare quicksort
int partition( gutui_t **a, int low, int high ){
	int l, r;
	gutui_t pivot, tmp;
	pivot.h = (*a)[low].h;
	pivot.g = (*a)[low].g;
	pivot.l = (*a)[low].l;
	l = low;
	r = high;
	while ( l < r ) {
     
		while( (*a)[l].g >= pivot.g) l++;
		while( (*a)[r].g < pivot.g ) r--;
		if ( l < r ) {
			tmp = (*a)[l];
			(*a)[l] = (*a)[r];
			(*a)[r] = tmp;
 		}
	}
  
	(*a)[low] = (*a)[r];
	(*a)[r] = pivot;
	return r;
}

//quicksort recursiv 
void quicksort( gutui_t **a, int low, int high ){
	int pivot;
	if ( high > low ){
	pivot = partition( a, low, high );
	quicksort( a, low, pivot-1 );
	quicksort( a, pivot+1, high );
	}
}
 
 
int main(){
	FILE *f,*out;
	int n, hmax, u, i, size = 0;
	int lev = 0;
	gutui_t gutuie;
	f = fopen("gutui.in", "r");
	out= fopen("gutui.out", "w");
	//citire
	fscanf(f,"%d %d %d\n",&n, &hmax, &u);
	gutui_t *v = (gutui_t*)calloc(n, sizeof(gutui_t));
	for (i = 0 ; i < n ;i ++){
		fscanf(f, "%d %d\n", &gutuie.h, &gutuie.g);
		if( gutuie.h <= hmax){
			gutuie.l = (hmax - gutuie.h) / u   + 1;
			v[size++] = gutuie;
		}
	}
 	//ordonare dupa greutate
	quicksort(&v,0,size-1);
	int *ocupat = (int *)calloc(hmax/u, sizeof(int)), val=0;
     	//ocuparea nivelelor la care se ia gutuia
	for(i = 0;i <size; i++)
	{  
		gutuie = v[i];
		if( !ocupat[gutuie.l-1]){
			val += gutuie.g;
			ocupat[gutuie.l-1] = 1;
		}
		else {
			lev = gutuie.l;
			while(lev > 0 && ocupat[lev-1]==1 )
				lev--;
			if(lev > 0 ){
				ocupat[lev-1] = 1;
				val+=gutuie.g;
			}
		}
	}
	fprintf(out, "%d", val);
	fclose(f);
	fclose(out);
	free(ocupat);
	//free(v);
	return 0;
}