Cod sursa(job #435407)

Utilizator Cristea_AdrianCristea Adrian Cristea_Adrian Data 7 aprilie 2010 14:01:32
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 3.01 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
        int nivel;
        int masa;
        } Gutui;


int compare(const void *c, const void *d)
{
     const Gutui *a = (const Gutui *)c;
     const Gutui *b = (const Gutui *)d;
     
     if(a->nivel!=b->nivel)
                         return (b->nivel - a->nivel);
     return(b->masa - a->masa);
}

int compare2 (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}



int main() {
    int h_max, nr_gutui, d_h;
    int i, j, k, min, pus=0, nr_niv,t;
    int *puse;
    Gutui *gut;
    int strans=0, niv_max;
    
    FILE *in, *out;

    in=fopen("gutui.in","r");
    out=fopen("gutui.out","w");
    
    fscanf(in,"%d ", &nr_gutui);
    fscanf(in,"%d ", &h_max);
    fscanf(in,"%d", &d_h);
    

    puse=(int *)malloc(1*sizeof(int));
    
    gut=(Gutui *)malloc(nr_gutui*sizeof(Gutui));
    
    for(i=0;i<nr_gutui;i++) {
         fscanf(in,"\n%d %d",&j, &gut[i].masa);
         gut[i].nivel=(j-1)/d_h+1;
         }
    
    qsort(gut, nr_gutui, sizeof(Gutui), compare);

    min=gut[nr_gutui-1].nivel;

                           
    niv_max=h_max/d_h;
    
    for(i=0;i<nr_gutui;i++) {
         if(gut[i].nivel+pus<=niv_max) {
                                       t=gut[i].masa;
                                       j=0;
                                      while(puse[j]<t && j<pus) {
                                                       j++;
                                                       }
                                      pus++;
                                      puse=(int*)realloc(puse, pus * sizeof(int));  
                                      for(k=pus-2;k>=j;k--)
                                                           puse[k+1]=puse[k];
                                      puse[k+1]=t;  

                                      }
         else if(gut[i].nivel+pus-niv_max==1)
              if(gut[i].masa>puse[0]) {
                                      j=1;
                                      while(puse[j]<gut[i].masa && j<pus) {
                                                       puse[j-1]=puse[j];
                                                       j++;
                                                       }
                                      puse[j-1]=gut[i].masa;
                                      }
         //for(j=0;j<pus;j++)
           //            printf("%d ",puse[j]);
         //printf("\n");                  
                            }
         
    //printf("\n");
    //for(i=0;i<nr_gutui;i++)
         //printf("%d %d\n",(gut[i]).nivel, (gut[i]).masa);
    
    for(i=0;i<pus;i++) {
                       //printf("%d ",puse[i]);
                       strans+=puse[i];
                       }
    
    //printf("\nmin=%d \nnivele=%d\nstrans=%d\n",min,niv_max, strans);
    
    fprintf(out,"%d",strans);

    fclose(in);
    fclose(out);
        
        //system("pause");
           
    return 0;
}