Cod sursa(job #632595)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 11 noiembrie 2011 18:48:48
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <stdio.h>
#define NMAX 100005

int N,heap[NMAX],moment[NMAX],noduri;//nr de noduri din heap
struct nod{
   int puf,dist;
}oaia[NMAX];


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

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

void urca(int poz){
   int x,aux;
    while((x=poz/2)&&(oaia[heap[x]].puf<oaia[heap[poz]].puf)){
         aux=heap[x];
         heap[x]=heap[poz];
         heap[poz]=aux;
         poz=x;
    }
}

void coboara_varful(){
    int max,fiu,x=1,c=1;
    do{
     fiu=c;    
     max=oaia[heap[c]].puf;
     //vecin in stanga
     if((x=2*c)>noduri)return;
     if(oaia[heap[x]].puf>max){
        fiu=x;
        max=oaia[heap[x]].puf;
     }
     if((x+=1)<=noduri && oaia[heap[x]].puf>max){
       fiu=x;
     }
     //interschimb fiu cu c
      max = heap[c];
      heap[c] = heap[x];
      heap[x] = max;

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


void push(int ind){
   noduri++;
   heap[noduri]=ind;
   urca(noduri);
}

void elimina_varf(){
   heap[1]=heap[noduri];
   noduri--;
   //printf("sunt inainte de coboara\n");
   coboara_varful();
   //printf("sunt dupa coboara\n");
}

int main(){
   int i,L,X,n;
   int  puf,dist;
   FILE *fin=fopen("lupu.in","r");
   FILE *fout=fopen("lupu.out","w");
  fscanf(fin,"%d%d%d",&n,&X,&L);
  for(i=1;i<=n;i++){
     fscanf(fin,"%d%d",&dist,&puf);
     if(X>=dist){
        N++;
        oaia[N].dist=dist;
        oaia[N].puf=puf;
        moment[N]=(X-oaia[N].dist)/L+1;
     }
  }
  //sortez vectorul oaia[] dupa moment
  sort(1,N);
  int j=1;
  long long suma=0;
  noduri=0;
  /*printf("maxmom=%d\n",moment[N]);
  for(i=N;i>0;i--)printf("%d ",moment[i]);
  printf("\n");*/

   for(i=moment[1];i>=1;i--){
     //printf("i=%d\n",i);
      while(moment[j]==i){//nu trebuie sa verific sa nu ies din vector...e cpacit cu 0
            //adaug toate oile din acest set in heap (adaug doar indicele)
            //printf("adaug si %d la heap\n",j);
            push(j);
            j++;
      }
      //printf("urmatoarea serie\n");
      if(noduri>=1){
         suma+=oaia[heap[1]].puf;
         elimina_varf();
      }
   }
   fprintf(fout,"%lld\n",suma);
  return 0;
}