Cod sursa(job #441539)

Utilizator TzibuTibuleac Andrei Sergiu Tzibu Data 12 aprilie 2010 22:59:13
Problema Gutui Scor 50
Compilator cpp Status done
Runda teme_upb Marime 2.15 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
 unsigned int niv,kg;
}GUTUIE;

int comp(const void *a,const void *b)
{
 unsigned int h1=((GUTUIE*)a)->niv;
 unsigned int h2=((GUTUIE*)b)->niv;
 if(h1==h2)
 {
   unsigned int kg1=((GUTUIE*)a)->kg;
   unsigned int kg2=((GUTUIE*)a)->kg;
   return kg2-kg1;  
 }
 return h2-h1;
}

void updateIns(unsigned int heap[],int index)
{
 int root=(index-1)/2;
 if(heap[root]>heap[index])
 {
   unsigned int aux;
   aux=heap[root];
   heap[root]=heap[index];
   heap[index]=aux;
   updateIns(heap,root);
 } 
}

void hIns(unsigned int heap[],unsigned int *dim,int val)
{
  heap[(*dim)]=val;
  updateIns(heap,(*dim));
  (*dim)++;  
}

void updateRem(unsigned int heap[],unsigned int dim,int root)
{
  int lNode=root*2+1,rNode=root*2+2,minNode=root; 
  if(lNode<dim&&heap[lNode]<heap[minNode])
    minNode=lNode;
  if(lNode<dim&&heap[rNode]<heap[minNode])
    minNode=rNode;   
  if(minNode!=root)
  {
    unsigned int aux=heap[minNode];
    heap[minNode]=heap[root];
    heap[root]=aux;
    updateRem(heap,dim,minNode);
  } 
}

void hRem(unsigned int heap[],unsigned int *dim)
{
  (*dim)--;
  heap[0]=heap[(*dim)];
  updateRem(heap,*dim,0);
}

int main()
{
  freopen("gutui.in","r",stdin);
  freopen("gutui.out","w",stdout);  
  
  unsigned int i,dim=0,sol=0,N,N2=0,H,U,niv,kg,heap[100000];
  GUTUIE vgutui[100000];
  
  scanf("%d %d %d",&N,&H,&U);
  //H/=U;
  for(i=0;i<N;i++)
  {
    scanf("%d %d",&niv,&kg);
    if(niv<=H) {vgutui[N2].niv=niv;vgutui[N2].kg=kg;N2++;}
    //vgutui[i].niv=(vgutui[i].niv-1)/U;
  }
  N=N2;
  qsort(vgutui,N,sizeof(GUTUIE),comp);  
  
  for(i=0;i<N;i++)
    if(vgutui[i].niv<=H)
    {      
      hIns(heap,&dim,vgutui[i].kg);
      //H--;
      H-=U;
      break;
    }
  i++;
  
  for(;(i<N)&&(H>=0);i++)
    if(vgutui[i].niv>H)
    {  
      if(vgutui[i].kg>heap[0])
      {
        hRem(heap,&dim);
        hIns(heap,&dim,vgutui[i].kg);
      }
    }
    else
    {      
      hIns(heap,&dim,vgutui[i].kg);
      H-=U;
      //H--;
    }
  for(i=0;i<dim;i++)
    sol+=heap[i];
  printf("%d",sol);
  return 0;
}