Cod sursa(job #922087)

Utilizator Kira96Denis Mita Kira96 Data 21 martie 2013 22:04:43
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<fstream>
#define NM 100100
#include<algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
struct el{ int t,a; }v[NM];
int cm(el A,el B){ return A.t>B.t; }
int TM,h[NM],i,x,d,j,l,n,aux;
long long sol;
int ma(int a,int b)
{
   if(h[a]>h[b])
      return a;
   return b;
}
void urca(int k)
{
   while(h[k]>h[k>>1]&&k>=2)
   {
     aux=h[k];
	 h[k]=h[k>>1];
	 h[k>>1]=aux;
      k>>=1;
   }
}
void coboara(int k)
{
   while((k<<1)<=x&&(h[k]<h[k<<1]||h[k]<h[(k<<1)+1]))
   {
      int c;
      if((k<<1)+1>x)
         c=(k<<1);
      else
         c=ma(k<<1,(k<<1)+1);
	  aux=h[k];
	  h[k]=h[c];
	  h[c]=aux;
      k=c;
   }
}
int main ()
{
   f>>n>>x>>l;
   for(i=1;i<=n;++i)
   {
      f>>d>>v[i].a;
      v[i].t=(x-d)/l+1;
      if(v[i].t>TM)
         TM=v[i].t;
   }
   j=1;
   sort(v+1,v+n+1,cm);
   x=0;
   for(i=TM;i>=1;--i)
   {
      while(v[j].t==i)
      {
         h[++x]=v[j].a;
         urca(x);
         j++;
      }
	  if(x<=0)
		  continue;
      sol+=h[1];
      h[1]=h[x--];
      coboara(1);
   }
   g<<sol;
   return 0;
}