Cod sursa(job #436166)

Utilizator prik_mihMihai Prica prik_mih Data 8 aprilie 2010 09:55:48
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.9 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;
    if(unu->clas==doi->clas) return (doi->weight-unu->weight);
    else return (unu->clas-doi->clas);
}
int compare1(const void *a,const void *b){
    return b-a;
}
int main(){
   // char s[20];
    int i,j,max_dif=0,depl=0,k=0,schimb=0;
    int *solutie;
    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));     
    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,sizeof(int));
   qsort(vect,n,sizeof(gutuie),my_compare);
  /* 
  for(i=0;i<n;i++)
      printf("\n%d %d %d ",vect[i].height,vect[i].weight,vect[i].clas);
     */ 
      int g=0;
      k=1;
   /*for( i = 0 ;i < n; i++,k++ )
       if(vect[i].clas==k){
                           */
       i=0;
       depl=0;
       while(i<n){//printf("\ni %d %d %d\n",i,depl,vect[i].clas);
                  k=vect[i].clas;
                  for( g=depl ; g < k ; g++)
                      solutie[depl++]=vect[i++].weight;
                  schimb=0;
               /*   for(g=0;g<depl;g++){
                     printf("%d ",solutie[g]);
                 }   
                printf("\n%d \n",i);
                 */
                 qsort(solutie,depl,sizeof(int),compare1);
                 for(g=i;vect[g].clas==k&&schimb<k;g++)
                     for(j=depl-2;j>=0&&schimb<k;j--)
                          if(solutie[j]<vect[g].weight) {
                                 solutie[j]=vect[g].weight;
                                 schimb++;
                                 break; 
                          }
                  i=g;
                  //k++; 
//                  qsort(solutie,depl,sizeof(int),compare1);
                  /*printf("\n");
                  for(g=0;g<depl;g++){
                     printf("%d ",solutie[g]);
                 }   
                 printf("\n");        
                 */
       }
       
                              
          int sum=0;
      for(i=0;i<depl;i++){
          sum+=solutie[i];
         // printf("%d ",solutie[i]);
          }
          
      fprintf(fout,"%d",sum);
          
     //getch();    
       
    return 0;
}