Cod sursa(job #438889)

Utilizator daniel.pleteaPletea Daniel daniel.pletea Data 11 aprilie 2010 02:26:51
Problema Lupul Urias si Rau Scor 52
Compilator c Status done
Runda Arhiva de probleme Marime 3.85 kb
#include <stdio.h>
//#include <conio.h>
#include <string.h>
#include <stdlib.h>


FILE* fs;
FILE* fd;
int N, max_height, height_inc,i,j,x,max_weight=0,increase=0,rest, cate_gutui, max, k;//,min,k, minmin,//kk,kkk,kkkk,maxh,r; 
int aux;

/*void insert(int value, nod arb)
{
     if(arb.value<value) 
     {
        aux = arb.value;
        arb.value=value;
        insert_end(
     }
}*/

typedef struct {
   int height;
   int weight;
} gutuie;

gutuie tree[100001];
//gutuie newtree[100001];

int compare (const void * a, const void * b)
{
  if(  ( (*(gutuie*)a).height - (*(gutuie*)b).height )  == 0 )
    return ( (*(gutuie*)b).weight - (*(gutuie*)a).weight );
  else return ( (*(gutuie*)a).height - (*(gutuie*)b).height ); 
}

typedef struct{
   int linii;
   int mat[10000][10000];
} evidenta;

evidenta evid;

int main(){
    
    fs = fopen("lupu.in","r");
    fd = fopen("lupu.out","w");
    
    if (fs==NULL) {
       printf("Eroare");
       exit (1);
    }
    
    if (fd==NULL) {
       printf("Eroare");
       exit (1);
    }
    
    
    
    //maxh=0;
    fscanf(fs,"%i",&N);   
    fscanf(fs,"%i",&max_height);
    fscanf(fs,"%i",&height_inc);
    rest = max_height%height_inc;
    max_height=max_height/height_inc;
    //printf("salut");
    for(i=0;i<N;i++){
       fscanf(fs,"%i",&x);
       if(x%height_inc>rest)
          tree[i].height = x / height_inc + 1;
       else
          tree[i].height = x / height_inc;
       fscanf(fs,"%i",&x);
       tree[i].weight = x;
    }
    
    
    
    qsort(tree,N,sizeof(gutuie),compare);
    
    for(i=N-1;i>=0;i--)
      if((tree[i].height+increase)<=max_height){
         increase++;
         //tree[i].getIt=1;
      }
    
    //linia=0;
    //marimea=0;
    //noua_linie = tree[0].height;
    evid.linii=0;
    evid.mat[0][0]=tree[0].height;
    evid.mat[0][1]=1;
    evid.mat[0][2]=3;
    evid.mat[0][3]=tree[0].weight;
    
    max_weight=0; 
    
    for(i=1;i<N;i++)
       if(evid.mat[evid.linii][0] == tree[i].height) 
       {
          evid.mat[evid.linii][1]++;
          evid.mat[evid.linii][evid.mat[evid.linii][1]+2] = tree[i].weight;
       }
       else
       {
           max = evid.mat[0][evid.mat[0][2]];
           k=0;
           for(j=1;j<=evid.linii;j++){
              if(evid.mat[j][evid.mat[j][2]]>max){
                 max = evid.mat[j][evid.mat[j][2]];
                 k=j;                                       
              }
           }
           max_weight = max_weight + max;
          // printf("%i max\n",max);
           evid.mat[k][2]++;
           increase--;
           
           evid.linii++;
           //evid.linii=1;
           evid.mat[evid.linii][0]=tree[i].height;
           evid.mat[evid.linii][1]=1;
           evid.mat[evid.linii][2]=3;
           evid.mat[evid.linii][3]=tree[i].weight;
       }
    while(increase>0){
       max = evid.mat[0][evid.mat[0][2]];
       k=0;
       for(j=1;j<=evid.linii;j++){
          if(evid.mat[j][evid.mat[j][2]]>max){
             max = evid.mat[j][evid.mat[j][2]];
             k=j;                                       
           }
       }
       max_weight = max_weight + max;
      // printf("%i max\n",max);
       evid.mat[k][2]++;
       increase--;
    }   
    //printf("salut");
    
   /* for(i=0;i<=evid.linii;i++){
       printf("\n %i %i : ", evid.mat[i][0], evid.mat[i][2]);
       for(j=0;j<evid.mat[i][1];j++)
          printf("%i ", evid.mat[i][j+3]);
       printf("\n");
    }      
    */
    //for(i=0;i<N;i++)
      //printf("%i %i \n", tree[i].height, tree[i].weight);
      
    
    
    
    
    //printf("salut %i ", increase);
   
    
       
   // printf("%i",max_weight);
    fprintf(fd,"%i",max_weight);
    
    fclose(fs);
    fclose(fd);
    
    //getch();
    
}