Cod sursa(job #437464)

Utilizator ctvalentinMarcu Valentin ctvalentin Data 9 aprilie 2010 19:24:29
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.82 kb
//#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
//int max[];
int N=0, H=0, U=1, nr=0, i, ii, j, k, aux=0, r, t, a=0, b=0, suma=0, **max, *diag;
FILE *f, *g;

int compare_doubles (const void *Y, const void *Z)
{
       int y = *((int *)Y);
       int z = *((int *)Z);
       if (y > z)
       {
               return -1;
       }
       else
       {
               if (y < z)
               {
                       return 1;
               }
               else
               {
                       return 0;
               }
       }
}

int main()
{
    f = fopen("gutui.in","r");
    if(!f) {printf("eroare f"); return 1;}
    g = fopen("gutui.out","w");
    if(!f) {printf("eroare g"); return 2;}
    fscanf(f,"%i", &N);
    fscanf(f,"%i", &H);
    fscanf(f,"%i", &U);
    nr = H/U;
    max = calloc ((nr+2),sizeof(int*));
    for(i=0;i<=nr+1;i++) { max[i] = calloc (N+2,sizeof(int));
                        }
      for(i=0;i<=nr+1;i++)                  
        for(j=0;j<=nr+1; j++) max[i][j]=0;                    
    for(i=0;i<N;i++)
    {
          
        // printf("\n nivelul %i : %i ", j, max[j][0]);
          fscanf(f,"%i", &a);  //a este inaltime initiala
          fscanf(f,"%i", &b);  //b este greutatea
          if(a<=H)
          {
            j= nr - a/U;          //j indica ordinea de evaluare
         // max[j] = calloc ((nr+1),sizeof(int));
          max[j][0]++; r=max[j][0];
          for(k=1;k<r;k++)
                if(b>max[j][k]) { aux=b; b=max[j][k]; max[j][k]=aux; }
          max[j][r]=b;
                   
          //max[j][max[j][0]] = b;
          //if(b > max[j-1]) max[j-1] = b;
        //  printf("\n nivelul %i : %i ", j, max[j][0]); //sleep(1);
          }
    }
    
    diag = calloc (N+2,sizeof(int));
    k=1;
    for(i=1;i<=N;i++) diag[i]=0;
    for(i=1;i<=N;i++)
         for(j=1;j<=i;j++)
           if(max[i][j]>0) { diag[k]=max[i][j]; k++;}
   
    qsort((void *)diag, N, sizeof(int), compare_doubles);
   // for(j=1;j<=N;j++) printf("%i ",diag[j]);
    for(j=1;j<=nr;j++) suma+=diag[j];
    //suma=max[1][1]; //prima data
    //printf("\nsuma partiala: %i ", suma);
 /*   for(i=1;i<=nr;i++) 
       { for(j=1;i<N+1;i++) 
          {printf(" %i ", *(max[i]+j));}
         printf("\n");
        } 
        printf("\n%i ", max[2][1]);
    for(i=1;i<nr;i++) 
        //for(k=1; k<=; k++)
            { 
                 //t=0; ii=i;
                 //suma += max[i][1];
                 for(ii=i+1;max[ii][0]=0, ii<nr; ii++)
                   {suma += max[i][ii-i]; printf("\nsuma partiala: %i ", suma);}
            }*/
    //suma += max[nr-1][1];
   // suma += max[nr][1];
    fprintf(g,"%i", suma);
   // printf("\n%i ", suma);
    free (max);
    fclose(f);
    fclose(g);
   // getch();
    return 0;
}