Cod sursa(job #632604)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 11 noiembrie 2011 19:34:45
Problema Lupul Urias si Rau Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <stdio.h>
#define NMAX 100005
#define MAXIM 10005
struct nod{
   int greutate, inaltime;
}v[NMAX];
int heap[NMAX];
int  noduri,H,U;


void urca(int loc){
   int x;
   int aux;
   while((x=loc/2) && v[heap[loc]].greutate>v[heap[x]].greutate){
      //interschimb nodul de pe locul loc cu tatal sau
      aux=heap[loc];
      heap[loc]=heap[x];
      heap[x]=aux;
      loc=x;
   }
}

void coboara(int loc){
   //cobor in fiul cel mai mic dintre cei doi
    int aux, x, y = 0;
    while (loc != y){
	y = loc;
	if ((x=y*2)<=noduri && v[heap[loc]].greutate<v[heap[x]].greutate) loc = x;
        x++;
	if (x<=noduri && v[heap[loc]].greutate<v[heap[x]].greutate) loc = x;
          aux = heap[loc];
	  heap[loc] = heap[y];
	  heap[y] = aux;
	}
}


void elimina(){
   //elimin varful heapului
   heap[1]=heap[noduri];
   noduri--;
   coboara(1);
}

int poz(int li, int ls){
    int ii=1,jj=0,a;
    nod aux;
    while(li<ls){
       if(v[li].inaltime<v[ls].inaltime){
          aux=v[li];
          v[li]=v[ls];
          v[ls]=aux;
          a=ii;
          ii=-jj;
          jj=-a;
       }
       li+=ii;
       ls+=jj;
    }
   return li;
}

void sortare(int li, int ls){
   if(li<ls){
      int k;
      k=poz(li,ls);
      sortare(li,k-1);
      sortare(k+1,ls);
   }
   
}

int pozitie=MAXIM-1;
char buff[MAXIM];//citesc bucati de cate maxim 10005 caractere

void cit(int &nr){
    nr=0;
    while(buff[pozitie]<'0' || buff[pozitie]>'9')//cat timp nu e cifra, treci mai departe
        if (++pozitie==MAXIM){
            fread (buff,1,MAXIM,stdin);
            pozitie=0;
        }
    while('0'<=buff[pozitie] && buff[pozitie]<='9'){//cat timp e cifra
        nr=nr*10+buff[pozitie]-'0';
        if (++pozitie==MAXIM){
            fread (buff,1,MAXIM,stdin);
            pozitie=0;
        }
     }
}

int main(){

  freopen("lupu.in","r",stdin);
  freopen("lupu.out","w",stdout);
  int N=0;
  scanf("%d%d%d",&N,&H,&U);
  int i,inaltime, greutate,ind=1;
  for(i=1;i<=N;i++){
     cit(inaltime);
     cit(greutate);
     if(inaltime<=H){
       v[ind].greutate=greutate;
       v[ind].inaltime=(H-inaltime)/U+1;
       ind++;
    }
  }

  N=ind-1;
  //sortez v descrescator dupa timp
  sortare(1,N);

  int indice=1;//locul in vector
  int j,suma=0;
  for(i=v[1].inaltime;i>0;i--){
       //adaug in heap tot ce face parte din seria i
      while(v[indice].inaltime==i){//sigur nu ies din vector, se termina cu un 0
             //bag nodul indice in heap
             noduri++;
             heap[noduri]=indice;
             urca(noduri);
             indice++;
      }
      //printf("urmatoarea serie\n");
      //afisez si extrag varful, daca heapul nu e vid
      if(noduri>=1){
         suma+=v[heap[1]].greutate;
         elimina();
      } 
  }
    printf("%d\n",suma);
return 0;
}