Cod sursa(job #547535)
#include<fstream>
#include<algorithm>
#define MaxN 100005
using namespace std;
ifstream f ("lupu.in");
ofstream g ("lupu.out");
struct sheep{
int time,lana;
};
sheep a[MaxN],h[MaxN];
int nh;
struct cmp{
bool operator()(const sheep &a,const sheep &b)
{ return a.time>b.time;
}
};
inline int maxim(int a,int b)
{
if(a>b)
return a;
return b;
}
inline bool compar(sheep a,sheep b)
{
if( a.lana == b.lana )
return a.time < b.time;
else
return a.lana > b.lana;
}
void swap( sheep &a , sheep &b )
{
sheep aux;
aux = a;
a = b;
b = aux;
}
inline void downHeap(int x)
{
int y = x;
if( x<<1 <= nh && compar(h[x<<1],h[y]) )
y = x<<1;
if( x<<1 < nh && compar(h[x<<1+1],h[y]) )
y = x<<1+1;
if( x != y )
{
swap(h[x],h[y]);
downHeap(y);
}
}
inline void upHeap(int x)
{
if( x <= 1 )
return ;
if( compar(h[x],h[x>>1]) )
{
swap(h[x],h[x>>1]);
upHeap(x>>1);
}
}
int main()
{
int n,X,L,x,y,i,j,dim=0,Tmax = -1;
long long rez =0;
f >> n >> X >> L;
for( i = 1 ; i <= n ; i++ )
{
f >> x >> y;
if( x <= X )
{
a[++dim].time = (X-x)/L+1;
a[dim].lana = y;
Tmax = maxim(Tmax,a[dim].time);
}
}
sort(a+1,a+dim+1,cmp());
for( i = Tmax ,j=1; i ; i-- )
{
for( ; j <= dim && a[j].time == i; j++ )
{
h[++nh] = a[j];
upHeap(nh);
}
while( nh && h[1].time < i )
{
h[1] = h[nh];
nh--;
downHeap(1);
}
if( nh )
{
rez += h[1].lana;
h[1] = h[nh];
nh--;
downHeap(1);
}
}
g << rez << '\n';
return 0;
}