Cod sursa(job #437263)

Utilizator daniel.rizeaRizea Daniel daniel.rizea Data 9 aprilie 2010 15:44:03
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.63 kb
#include<stdio.h>
#include<list>
#include<stdlib.h>
#include<algorithm>
#include<vector>
using namespace std;
FILE* fin;
FILE* fout;

typedef struct gut{

    unsigned int greutate;
    unsigned int tmp;

}*gutui;
// functie comparator pentru sortare qsort cu functia din clasa list
bool compare_desc(gut first,gut second)
{


  if (first.tmp < second.tmp ) return true;
  else
      if(first.tmp == second.tmp)
      {  if(first.greutate<=second.greutate)
          return true;
      else
          return false;
      }

  return false;
}
// comparator ce ajuta la crearea min_heap
bool heap_min(unsigned int first,unsigned int second)
{


  if ( first > second ) return true;
 
  return false;
}

int main(){

 

   unsigned int h,u,a,g;
   unsigned int suma=0;
   unsigned int v[]={0};

   unsigned int n,i,max;
   int t;


    fin=fopen("gutui.in","r");
    fout=fopen("gutui.out","w");
    list<gut> cos;
    list<gut>::iterator it;

    

    fscanf(fin,"%d %d %d\n",&n,&h,&u);
 gut *aux;

 if(h%u==0)
 {
     t=0;
 max=h/u;

 }else
 {max=h/u+1;
 t=1;
 }
    for(i=0;i<n;i++)
    {
     aux=(gut*)malloc(sizeof(struct gut));


        fscanf(fin,"%u %u\n",&a,&g);
// obtinerea momentului de timp maxim in care se poate culege gutuia
        if(a+(max-t-(a/u))*u<=h)

        aux->tmp=max-t-(a/u-1);
        else
            aux->tmp=max-t-(a/u);

      
        aux->greutate=g;
        cos.push_back(*aux);

        free(aux);

    }

    cos.sort(compare_desc);





    unsigned int *matrice;
    matrice=(unsigned int*)calloc(max+1,sizeof(unsigned int));
    
   

    
   unsigned int nivel=0;
    int ind=0;
   unsigned  int top,poz;
   
    it=cos.begin();

    ind=it->tmp;
    poz=it->tmp;
    top=it->tmp;
 
    
   

    nivel=0;

    // creare heap;
vector<unsigned int> luate(v,v+0);
make_heap(luate.begin(),luate.end(),heap_min);

    
    for(i=1;i<=n;i++)
    {

  
        if(nivel<it->tmp){
         // se insereaza valoarea in heap
            suma=suma+it->greutate;
            luate.push_back(it->greutate);
            push_heap(luate.begin(),luate.end(),heap_min);
            nivel++;
        }
        else
        {if(luate.front()<it->greutate)

            // se socate valoarea mica din heap si din suma sise inlocuieste cu noua greutate

            suma=suma-luate.front()+it->greutate;

        pop_heap(luate.begin(),luate.end(),heap_min);
        luate.pop_back();

         luate.push_back(it->greutate);
         push_heap(luate.begin(),luate.end(),heap_min);



        }

        
      
        it++;
    }

 
    

       fprintf(fout,"%u",suma);


      
       free(matrice);
     



        fclose(fin);
        fclose(fout);

    return 0;
}