Cod sursa(job #632493)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 11 noiembrie 2011 12:50:56
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.27 kb
#include <stdio.h>
#define NMAX 100005

struct nod{
   int greutate, inaltime;
}v[NMAX];
int heap[NMAX],T[NMAX];
int  noduri=1,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]=noduri;
   noduri--;
   coboara(1);
}

int poz(int li, int ls){
    int ii=1,jj=0,a;
    nod aux;
    while(li<ls){
       if(T[li]<T[ls]){
          aux=v[li];
          v[li]=v[ls];
          v[ls]=aux;
     
          a=T[li];
          T[li]=T[ls];
          T[ls]=a;
          

          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 main(){
  FILE *fin=fopen("gutui.in","r");
  FILE *fout=fopen("gutui.out","w");
  int N=0;
  fscanf(fin,"%d%d%d",&N,&H,&U);
  int i,inaltime, greutate,ind=1;
  int tmax=-1;
  for(i=1;i<=N;i++){
     fscanf(fin,"%d%d",&inaltime,&greutate);
     if(inaltime<=H){
       v[ind].greutate=greutate;
       v[ind].inaltime=inaltime;
       T[ind]=(H-inaltime)/U+1;
       if(T[ind]>tmax)tmax=T[ind];
       ind++;
    }
  }

  N=ind-1;
  //sortez v descrescator dupa timp
  sortare(1,N);
  int indice=1;//locul in vector
  int j,suma=0;
  for(i=tmax;i>=1;i--){
       //adaug in heap tot ce face parte din seria i
      while(indice<=N && T[indice]==i){
             //bag nodul indice in heap
             heap[noduri]=indice;
             urca(noduri);
             noduri++;
             indice++;
      }
      //afisez si extrag varful, daca heapul nu e vid
      if(noduri>1){
         suma+=v[heap[1]].greutate;
         elimina();
      } 
  }
    fprintf(fout,"%d\n",suma);
return 0;
}