Cod sursa(job #436698)

Utilizator prik_mihMihai Prica prik_mih Data 8 aprilie 2010 20:16:33
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 3.31 kb
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
//using namespace std;
int n,h,u;
typedef struct {
        unsigned int height;
        unsigned int weight;
        unsigned int clas;
        }gutuie;
gutuie *vect;

int my_compare(const void *a,const void *b){
    gutuie *unu=(gutuie *) a;
    gutuie *doi=(gutuie *) b;
    return (doi->weight-unu->weight);
}
int comp(const void * aa,const void * bb) 
{ int *a=(int *) aa;
  int *b=(int *) bb;
  if (*a==*b)
    return 0;
  else
    if (*a < *b)
        return -1;
     else
      return 1;
}
int main(){
    int i,j,k=0;
    unsigned int max_dif=0;;
    long solutie=0;
    unsigned char *cules;
    FILE *fin=fopen("gutui.in","r");
    FILE *fout=fopen("gutui.out","w");
    fscanf(fin,"%d",&n);
    fgetc(fin);
    fscanf(fin,"%d",&h);
    fgetc(fin);
    fscanf(fin,"%d",&u);
   
    //respect restrictile
    if(n<1||n>100000) 
         return 1;
    vect=(gutuie *)malloc(n*sizeof(gutuie));     
    //cules=(short *)calloc(n,sizeof(short));
    for(i=0;i<n;i++){
       fgetc(fin);
       fscanf(fin,"%d",&vect[i].height);
       fgetc(fin);
       fscanf(fin,"%d",&vect[i].weight);
       vect[i].clas=(h-vect[i].height)/u+1;
       if(vect[i].clas>max_dif) 
       max_dif=vect[i].clas;
   }
   //solutie=(int *)calloc(max_dif+1,sizeof(int));
   cules=(unsigned char *)calloc(max_dif+1,sizeof(unsigned char));
   qsort(vect,n,sizeof(gutuie),my_compare);
  
  /*for(i=0;i<n;i++)
      printf("\n%d %d %d %d ",vect[i].height,vect[i].weight,vect[i].clas,max_dif);
     */
    
      
      i=0;
      int nrgutui=0;
    for(i=0;i<n && nrgutui<=max_dif;i++){
              k=vect[i].clas;
              if(cules[k]==0){
                   solutie+=vect[i].weight;
                   cules[k]=1;
                   nrgutui++;
                   }
              else 
                 for(j=k-1;j>=1;j--)
                    if(cules[j]==0){
                        solutie+=vect[i].weight;
                        cules[j]=1;
                        nrgutui++;
                        break;
                    }
   }                 
                                  
                                           
                   /*
   metoda pe care am abordat-o prima data
   dar care era prea lenta datorita qsortului de mai jos
   in teorie si ea functioneaza
   
      while(i<n){
                  k=vect[i].clas;
                  for( g=depl ; g < k && i < n; g++)
                      solutie[depl++]=vect[i++].weight;
                  schimb=0;
                   qsort(solutie,depl,sizeof(int),comp);
                              
                 for(g=i;vect[g].clas==k&&schimb<k;g++)
                     for(j=0;j<depl&&schimb<k;j++)
                          if(solutie[j]<vect[g].weight) {
                                 solutie[j]=vect[g].weight;
                                 schimb++;
                                 break; 
                          }
                  i=g;
         
       }
       
                 */            
      /*    int sum=0;
      for(i=1;i<=max_dif;i++){
          sum+=solutie[i];
          //printf("%d ",solutie[i]);
          }
        */  
      fprintf(fout,"%ld",solutie);
          
    //  getch();    
       
    return 0;
}