Cod sursa(job #437104)

Utilizator angel_pacPetre Andreea Cristina angel_pac Data 9 aprilie 2010 12:56:34
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.4 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;
}