Cod sursa(job #439087)

Utilizator Cristea_AdrianCristea Adrian Cristea_Adrian Data 11 aprilie 2010 12:46:42
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.94 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 (a->nivel - b->nivel);
     return(b->masa - a->masa);
}

int main() {
    int h_max, nr_gutui, d_h;
    int i, j, k, t, nr_puse=0;
    int *puse;
    Gutui *gut;
    int strans=0;
    
    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);
        
    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=(h_max-j)/d_h+1;
         }
    
    qsort(gut, nr_gutui, sizeof(Gutui), compare);
    
    k=gut[nr_gutui-1].nivel;
    puse=(int *)calloc(k,sizeof(int));
  
    for(i=0;i<nr_gutui;i++) {
         if(gut[i].nivel-nr_puse>0) {
              t=gut[i].masa;
              j=0;
              while(puse[j]<t && j<nr_puse) {
                   j++;
              }
              nr_puse++;
              for(k=nr_puse-2;k>=j;k--)
                   puse[k+1]=puse[k];
              puse[k+1]=t;  
         }
         else 
              if(gut[i].nivel-nr_puse==0)
                   if(gut[i].masa>puse[0]) {
                        t=gut[i].masa;
                        j=1;
                        while(puse[j]<t && j<nr_puse) {
                             puse[j-1]=puse[j];
                             j++;
                        }
                        puse[j-1]=t;
                   }                  
    }
    
    for(i=0;i<nr_puse;i++)
         strans+=puse[i];
    
    fprintf(out,"%d",strans);

    fclose(in);
    fclose(out);
           
    return 0;
}