Cod sursa(job #441157)

Utilizator TzibuTibuleac Andrei Sergiu Tzibu Data 12 aprilie 2010 19:53:26
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 2.12 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[],int *dim,int val)
{
  heap[(*dim)]=val;
  updateIns(heap,(*dim));
  (*dim)++;
}

int vfChild(unsigned int heap[],int dim,int index,int c)
{
  if(c<dim&&heap[c]<heap[index])
  {
    unsigned int aux;
    aux=heap[c];
    heap[c]=heap[index];
    heap[index]=aux;    
    return 1;
  }
  return 0;
}

void updateRem(unsigned int heap[],int dim,int index)
{
  int c=index*2+2;  
  if(vfChild(heap,dim,index,c))
  {
    updateRem(heap,dim,c);
    return;
  }
  c=index*2+1;
  if(vfChild(heap,dim,index,c))
  {
    updateRem(heap,dim,c);
    return;
  }
}

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

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