Cod sursa(job #778282)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 14 august 2012 13:46:38
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<fstream>
#include<algorithm>
using namespace std;

struct sheep {int dist; int wool;};
int h[100002];
sheep v[100002];
int t[100002];
int n,x,l,d,a,sum,sizeheap,step[100002],r,i,j,nrsteps,nrc,tmax;
char buff[100];

struct comp
{bool operator()(const sheep &a, const sheep &b) const
       {
       return (a.dist<b.dist);
       }
};

void swap(int z1, int z2)
{int 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]<h[z])
    {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]>h[2*z])
     son=2*z+1;}
else
  return;     
if(h[z]<h[son])
  {swap(z,son);
   z=son;}
else
  son=0;    
}while(son);
}

int get_number()
{int nrn=0;
while(buff[nrc]<='9' && buff[nrc]>='0')
   {nrn=10*nrn+buff[nrc]-'0';
   nrc++;}
return nrn;
}

int main()
{freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
gets(buff);
nrc=0;
n=get_number();
nrc++;
x=get_number();
nrc++;
l=get_number();
for(i=1; i<=n; i++)
  {gets(buff);
   nrc=0;
   d=get_number();
   nrc++;
   a=get_number();
   sheep q;
   q.dist=d;   q.wool=a;
   v[i]=q;
   t[i]=(x-d)/l;
   if(t[i]>tmax)
      tmax=t[i];
  }

sort(v+1, v+n+1, comp());

i=1;
for(j=tmax; j>=0; j--)
 {
  while(((x-v[i].dist)/l)==j)  {sizeheap++;  h[sizeheap]=v[i].wool; swim(sizeheap);  i++;}
  if(sizeheap)
  {sum+=h[1];
   swap(1,sizeheap);
   sizeheap--;
   sink(1);
   }
}
  
printf("%d",sum);   
return 0;
}