Cod sursa(job #440475)

Utilizator catalin_olariOlari Catalin Georgel catalin_olari Data 12 aprilie 2010 02:10:41
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 4.14 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;
     return gutui;
}
short citire()
{
     FILE *f=fopen("gutui.in","rt");
     long i;
     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;
     }       
     fscanf(f,"%li%li",&gutui[0].inaltime,&gutui[0].greutate);    
     for(i=1;i<N;i++)
          fscanf(f,"%li%li",&gutui[i].inaltime,&gutui[i].greutate);    
     fclose(f);
     return 0;
}
     
int sort_function(const void *a,const void *b)
{
    fruct *A=(fruct*)a;
    fruct *B=(fruct*)b;
    return B->inaltime - A->inaltime;
}




/*
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 && gutui[t].inaltime <= H)
       { 
         nr++;
         G+=gutui[t].greutate;
         
         for(j=indice;j<max;j++)
            v[j]=v[j]-1;
         for(j=0;j<indice;j++)
             if( v[j] > v[indice] )
                 v[j]=v[indice];
                 
       }
       t++;

      }
     

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

long cautare_binara(long *v,long s,long d,long elem)
{
       if(s < d)
        {    if(v[ (s+d)/2 ] > elem)
                  return cautare_binara(v,s,(s+d)/2,elem);
            else
                if(v[ (s+d)/2 ] < elem)
                      return cautare_binara(v,(s+d)/2+1,d,elem);
                else
                    return s;                
        }
       return s;
}
void afiseaza(long *v,int n)
{
     int i;
     printf("\n\n");
     for(i=0;i<n;i++)
       printf("%li ",v[i]);
}
long* actualizeaza(long *v,long begin,long k,long elem)
{
      long poz=cautare_binara(v,begin,k-1,elem),i;
     //printf("[%li %li]\nINAINTE",poz,k);
      //afiseaza(v,k);
      
      for(i=k;i>poz;i--)
         v[i]=v[i-1];
    //  printf("\nDupa");
     // afiseaza(v,k+1);
      if(k==0 || begin==k || elem < v[poz])
       {
      //        printf("ok");
                v[poz]=elem;
       }
      else
          v[poz+1]=elem;
          
    //  printf("%li",v[0]);
      return v;
}




long solve()
{
     long i,k=0,*v,begin=0;
     long G=0;
     v=(long*)calloc(N,sizeof(long));
     if(!v)
           return -1;
     for(i=0;i<N;i++)
       if( gutui[i].inaltime <= H)
        // if( ((H - gutui[i].inaltime) / U) >= (k - begin) )
         {
                                v=actualizeaza(v,begin,k++,gutui[i].greutate);
                                H-=U;
                                //G+=gutui[i].greutate;
                               
                              
         }
        else
          if(begin < k)
           if( gutui[i].greutate > v[begin] )
           {
        //       G-=v[begin];
        v[begin]=0;
               begin++;
               v=actualizeaza(v,begin,k++,gutui[i].greutate);
//               G+=gutui[i].greutate;
                        
                                              
           }
 
for(i=0;i<k;i++)
  G=G+v[i];
     return G;
}            


     

int main()
{
     if( citire() != 0)
                 return -1;
     qsort((void*)gutui,N,sizeof(fruct),sort_function);

     FILE *f=fopen("gutui.out","wt");
     fprintf(f,"%li",solve());
     fclose(f);
     int t,i;
  /*   long *v=(long*)calloc(40,sizeof(long));
     for(i=0;i<30;i++)
     {
           scanf("%i",&t);
           v=actualizeaza(v,0,i,t);
           afiseaza(v,i+1);
           
     }           */
     
     
     gutui=destroy(gutui);
     return 0;
}