Cod sursa(job #778149)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 14 august 2012 00:54:23
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<fstream>
using namespace std;

struct sheep {int dist; int wool;};
sheep h[100002];
int n,x,l,d,a,sum,sizeheap,step[100002],r,i;

void swap(int z1, int z2)
{sheep aux=h[z1];
h[z1]=h[z2];
h[z2]=aux;
}

void swim(int z)
{int father;
 do{father=0;
 if((z/2)>=1)
   father=z/2;
 else 
   return;  
 if(h[father].wool<h[z].wool)
    {swap(father,z);
     z=father;}
 else 
    {if(h[father].wool==h[z].wool && h[father].dist<h[z].dist)
    {swap(father,z);
     z=father;}
    else
       father=0;}
 }while(father);
}

void sink(int z)
{int son;
do{son=0;
if(2*z<=sizeheap)
  {son=2*z;
   if(2*z+1<=sizeheap && (h[2*z+1].wool>h[2*z].wool || (h[2*z+1].wool==h[2*z].wool && h[2*z+1].dist>h[2*z].dist)))
     son=2*z+1;}
else
  return;     
if(h[z].wool<h[son].wool)
  {swap(z,son);
   z=son;}
else
  {if(h[son].wool==h[z].wool && h[son].dist>h[z].dist)
    {swap(son,z);
     z=son;}
    else
       son=0;}     
}while(son);
}

int main()
{freopen("lupu2.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d %d %d",&n,&x,&l);
for(i=1; i<=n; i++)
  {scanf("%d %d",&d,&a);
   sizeheap++;
   sheep q;
   q.dist=d;   q.wool=a;
   h[sizeheap]=q;
   swim(sizeheap);}
   
while(sizeheap)
{r=((x-h[1].dist)/l)+1;
while(r>0 && step[r]==1)  r--;
if(r>0 && step[r]==0)
{step[r]=1;
 sum+=h[1].wool;
}
swap(1,sizeheap);
sizeheap--;
sink(1);
}   
  
printf("%d",sum);   
return 0;
}