Cod sursa(job #922087)
#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;
}