Cod sursa(job #435883)

Utilizator angel_pacPetre Andreea Cristina angel_pac Data 7 aprilie 2010 22:19:13
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.01 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++;
    while( (*a)[right].g < pivot.g ) right--;
    if ( left < right ) {
						tmp = (*a)[left];
						(*a)[left] = (*a)[right];
						(*a)[right] = tmp;
					    }
    }
 
  (*a)[low] = (*a)[right];
  (*a)[right] = pivot;
  return right;
  }

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");
	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){
			gutuie.l = (hmax - gutuie.h) / u   + 1;
			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-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;
				
			 }
		}
		//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;
}