Cod sursa(job #632535)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 11 noiembrie 2011 15:53:42
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 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;
    //daca pot sa cobor prin stanga
      if((x=2*c)>noduri)return;
      if(oaia[heap[c]].puf<oaia[heap[x]].puf){max=oaia[heap[x]].puf;fiu=x;}
      if(((++x)<=noduri) && (oaia[heap[x]].puf>max)){fiu=x;}
      //interschimba c cu fiu
        x=heap[c];
        heap[c]=heap[fiu];
        heap[fiu]=x;
        c=fiu;
      
    }while(fiu!=c);
}


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,maxmom=-1;//momentul maxim/cate seturi de oi exista
   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;
        if(moment[N]>maxmom)maxmom=moment[N];
     }
  }
  //sortez vectorul oaia[] dupa moment
  sort(1,N);
  int j=1;
  long long suma=0;
  noduri=0;
  //printf("maxmom=%d\n",maxmom);
   for(i=maxmom;i>=1;i--){
     //printf("i=%d\n",i);
      while(j<=N && moment[j]==i){
            //adaug toate oile din acest set in heap (adaug doar indicele)
            push(j);
            j++;
      }
      if(noduri>=1){
         suma+=oaia[heap[1]].puf;
         elimina_varf();
      }
   }
   fprintf(fout,"%lld\n",suma);
  return 0;
}