Cod sursa(job #439880)

Utilizator catalin_olariOlari Catalin Georgel catalin_olari Data 11 aprilie 2010 20:10:03
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.05 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct 
{
        long inaltime,greutate;
}fruct;

long N;
long H,U;
fruct *gutui;

fruct* destroy(fruct *gutui)
{
     free(gutui);
     gutui=NULL;
}
short citire()
{
     FILE *f=fopen("gutui.in","rt");
     if(!f)
     {
           printf("File not found!");
           return -1;
     }
     fscanf(f,"%li%li%li",&N,&H,&U);
     gutui=(fruct*)calloc(N,sizeof(fruct));

     if(!gutui)
     {
               printf("Alocare esuata");
               return -2;
     }
     long i;
     
     fscanf(f,"%li%li",&gutui[0].inaltime,&gutui[0].greutate);
     long min=gutui[0].inaltime;
     for(i=1;i<N;i++)
     {
          fscanf(f,"%li%li",&gutui[i].inaltime,&gutui[i].greutate);
          if(gutui[i].inaltime < min)
                               min=gutui[i].inaltime;
     }
     fclose(f);
     return min;
}
     
int sort_function(const void *a,const void *b)
{
    fruct *A=(fruct*)a;
    fruct *B=(fruct*)b;
    return B->greutate - A->greutate;
}





long solve(long max)
{
     long *v,t=0,indice,j,G=0,i,nr=0;
     v=(long*)calloc(max,sizeof(long));
     if(!v)
     {
           printf("Alocare esuata!");
           return -1;
     }

     for(i=0;i<max;i++)
        v[i]=i+1;
     
    
     
     while(t < N  &&  nr < max)
     {
             
       indice=(H - gutui[t].inaltime)/U;
       if(v[indice] > 0)
       { 
         nr++;
         G+=gutui[t].greutate;
         for(j=indice;j<max;j++)
            v[j]--;
         for(j=0;j<indice;j++)
             if( v[j] > v[indice] )
                 v[j]=v[indice];
       }
       t++;

       
      }
     
     
     free(v);
     v=NULL;
     return G;
}
    

int main()
{
     long max;
     if( (max=citire()) < 0)
                 return -1;
     qsort((void*)gutui,N,sizeof(fruct),sort_function);
     
     max=(H - max)/U+1;
     FILE *f=fopen("gutui.out","wt");
     fprintf(f,"%li",solve(max));
     fclose(f);
     gutui=destroy(gutui);
     return 0;
}