Cod sursa(job #437093)

Utilizator angel_pacPetre Andreea Cristina angel_pac Data 9 aprilie 2010 12:47:41
Problema Gutui Scor 40
Compilator c Status done
Runda teme_upb Marime 1.83 kb
//Petre Andreea 
#include <stdio.h>
#include <stdlib.h>
//structura gutuie :P
typedef struct gutui{
	int g, h, l;
}gutui_t;
//partition de la quick_sort
int partition( gutui_t **a, int low, int high ){
	int l, r;
	gutui_t pivot, tmp;
	pivot = (*a)[low];
	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;
}

//quick-sort 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(){
	//fisiere I\O
	FILE *f,*out;
	//variabile
	int n, hmax, u, i, size = 0, val = 0;
	int lev = 0;
	gutui_t gutuie;
	gutui_t *v;
	int *ocupat;

	f = fopen("gutui.in", "r");
	out= fopen("gutui.out", "w");

	fscanf(f,"%d %d %d\n",&n, &hmax, &u);

	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;
			
		}
	}
	//sortare rapida
	quicksort(&v,0,size-1); //O(nlogn) in cazul mediu...in cel mai rau caz O(n^2)
	
	//vector ce imi spune daca un nivel a fost ocupat deja sau nu
	ocupat = (int *)calloc(hmax/u, sizeof(int)), val=0;

	for(i = 0; i <size; i++) //O(n)
	{	
		gutuie = v[i];	//O(1)
		if( !ocupat[gutuie.l-1]){//O(1)
				val += gutuie.g;
				ocupat[gutuie.l-1] = 1;
		}
		else {
			 lev = gutuie.l;	//O(1)
			 while(lev > 0 && ocupat[lev-1]==1 ) //O(hmax/u) in cel mai rau caz..deci un O(m)
					lev--;
			 if(lev > 0 ){	//O(1)
					ocupat[lev-1] = 1;
					val+=gutuie.g;
				
			 }
		}
	}
	fprintf(out, "%d", val);
	free(ocupat);
	free(v);
	fclose(f);
	fclose(out);
	return 0;
}