Cod sursa(job #922068)

Utilizator Kira96Denis Mita Kira96 Data 21 martie 2013 21:55:38
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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 sol,TM,h[NM],i,x,d,j,l,n;
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>>1))
   {
      h[k]^=h[k>>1]^=h[k]^=h[k>>1];
      k>>=1;
   }
}
void coboara(int k)
{
   while((k<<1)<=x&&(h[k]<h[k<<1]||h[k]<h[(k<<1)+1]))
   {
      int c;
      if(h[(k<<1)+1]==0)
         c=(k<<1);
      else
         c=ma(k<<1,(k<<1)+1);
      h[k]^=h[c]^=h[k]^=h[c];
      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);
   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]^=h[1]^=h[x];
      --x;
      coboara(1);
   }
   g<<sol;
   return 0;
}