Cod sursa(job #437058)

Utilizator daniel.rizeaRizea Daniel daniel.rizea Data 9 aprilie 2010 11:45:43
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 3.05 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;
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;
}


int main(){

 

   unsigned int h,u,a,g,maxim;

    fin=fopen("gutui.in","r");
    fout=fopen("gutui.out","w");
    unsigned int n,i,j,max;
    int t;

    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);

        if(a+(max-t-(a/u))*u<=h)

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

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

        free(aux);

    }

    cos.sort(compare_desc);

 //  for (it=cos.begin(); it!=cos.end(); ++it)
   //     printf("%u %u\n",it->greutate,it->tmp);




    unsigned int *matrice;
    matrice=(unsigned int*)calloc(max+1,sizeof(unsigned int));
    
    printf("max=%d\n",max);

    int suma=0;
    int timp=n;
    int ind=0;
   unsigned  int top,poz,full=0;
    unsigned int min;
    unsigned int pozMin=0;
    it=cos.begin();

    ind=it->tmp;
    poz=it->tmp;
    top=it->tmp;
    unsigned int v[]={};
    vector<unsigned int> luate(v,v+6);
    
  /*  printf("heapuri\n");
    make_heap(luate.begin(),luate.end());
    
    for(i=0;i<luate.size();i++)
        printf("%d ",luate[i]);
    printf("\n");

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

     for(i=0;i<luate.size();i++)
        printf("%d ",luate[i]);
    printf("\n");
    luate.push_back(12);
    push_heap(luate.begin(),luate.end());
     luate.push_back(32);
    push_heap(luate.begin(),luate.end());
 luate.push_back(22);
    push_heap(luate.begin(),luate.end());

    for(i=0;i<luate.size();i++)
        printf("%d ",luate[i]);
    printf("\n");
*/

    unsigned int nivel;
    for(i=1;i<=n;i++)
    {
        
        if(i<=it->tmp){
            suma=suma+it->greutate;
            luate.push_back(it->greutate);
            push_heap(luate.begin(),luate.end());

        }
        else
        {if(luate.front()<it->greutate)
            suma=suma-luate.front()+it->greutate;

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

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



        }

        
      
        it++;
    }

  /*  printf("\n");
      for(i=1;i<=top;i++)
           printf("%d ",i);
    printf("\n");
     for(i=1;i<=top;i++)
         printf("%d ",matrice[i]);


    printf("\n");
    */
      printf("%u\n",suma);

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


      
       free(matrice);
     



        fclose(fin);
        fclose(fout);

    return 0;
}