Cod sursa(job #435379)

Utilizator angel_pacPetre Andreea Cristina angel_pac Data 7 aprilie 2010 13:05:03
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 2.24 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct gutui{
	int g, h, l;
}gutui_t;

int partition( gutui_t **a, int low, int high )
  {
  int left, right;
  gutui_t pivot, tmp;
  pivot.h = (*a)[low].h;
  pivot.g = (*a)[low].g;
  pivot.l = (*a)[low].l;
  left = low;
  right = high;
  while ( left < right ) {
    
    while( (*a)[left].g >= pivot.g) left++;
    /* Move right while item > pivot */
    while( (*a)[right].g < pivot.g ) right--;
    if ( left < right ) {
						tmp = (*a)[left];
						(*a)[left] = (*a)[right];
						(*a)[right] = tmp;
					    }
    }
  /* right is final position for the pivot */
  (*a)[low] = (*a)[right];
  (*a)[right] = pivot;
  return right;
  }

void quicksort( gutui_t **a, int low, int high )
  {
  int pivot;
  /* Termination condition! */
  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");
	fscanf(f,"%d %d %d\n",&n, &hmax, &u);
	//printf("%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){
			if( gutuie.h == hmax)
				gutuie.l = 0;
				else{	
					if(gutuie.h%u)
							gutuie.l = (hmax/u) - gutuie.h/u-1;
					else
							gutuie.l = (hmax/u) - gutuie.h/u;
					}
			v[size++] = gutuie;
			
		}
	}
	//for(i = 0; i < size ;i++){
		//printf("%d %d %d\n", v[i].h, v[i].g, v[i].l);
	//}
	quicksort(&v,0,size-1);
	//printf("\n");
	//for(i = 0; i < size ;i++){
		//printf("%d %d %d\n", v[i].h, v[i].g, v[i].l);
	//}
	
	int *ocupat = (int *)calloc(hmax/u, sizeof(int)), val=0;
	//int  j;
	
	for(i = 0;i <size; i++)
	{	
		gutuie = v[i];
		if( !ocupat[gutuie.l]){
				val += gutuie.g;
				ocupat[gutuie.l] = 1;
		}
		else {
			 lev = gutuie.l;
			 while(lev >= 0 && ocupat[lev]==1 )
					lev--;
			 if(lev >= 0 ){
					ocupat[lev] = 1;
					val+=gutuie.g;
				
			 }
		}
		/*printf("greutate = %d\n", gutuie.g);
		printf("val = %d\n", val);
		for(j = 0; j< hmax/u; j++)
			printf("%d ", ocupat[j]);
		printf("\n");*/
	}
	fprintf(out, "%d", val);
	fclose(f);
	fclose(out);
	return 0;
}