Pagini recente » Cod sursa (job #905049) | Profil LittleGreenMen | Cod sursa (job #2485233) | Cod sursa (job #383538) | Cod sursa (job #547570)
Cod sursa(job #547570)
#include<fstream>
#include<algorithm>
#define MaxN 100001
using namespace std;
ifstream f ("lupu.in");
ofstream g ("lupu.out");
struct sheep{
int dist,lana;
};
sheep a[MaxN];
int n,N,X,L,Tmax,nh,h[MaxN];
long long rez;
bool cmp(sheep a , sheep b)
{
if( a.dist == b.dist )
return a.lana > b.lana;
else
return a.dist < b.dist;
}
int maxim(int a,int b)
{
if( a > b )
return a;
return b;
}
inline void upHeap(int x)
{
if( x > 1 )
if( h[x] > h[x>>1] )
{
int aux = h[x];
h[x] = h[x>>1];
h[x>>1] = aux;
upHeap(x>>1);
}
}
inline void downHeap(int x)
{
int m = x;
if( x << 1 <= nh && h[x<<1] > h[m] )
m = x<<1;
if( x << 1 + 1 <= nh && h[x<<1+1] > h[m] )
m = x<<1 + 1;
if( m != x)
{
int aux = h[x];
h[x] = h[m];
h[m] = aux;
downHeap(m);
}
}
int main()
{
int i,j,x,y;
f >> n >> X >> L;
Tmax = -1;
for( i = 1 ; i <= n ; i++ )
{
f >> x >> y;
if( x <= X )
{
N++;
a[N].dist = (X-x)/L +1;
a[N].lana = y;
Tmax = maxim(Tmax,a[N].dist);
}
}
sort(a+1,a+N+1,cmp);
for( j = Tmax , i = 1 ; j; j-- )
{
for( ; i <= N && a[i].dist == j ; i++ )
{
nh++;
h[nh] = a[i].lana;
upHeap(nh);
}
if( nh )
{
rez += h[1];
h[1] = h[nh];
nh--;
downHeap(1);
}
}
g << rez << '\n';
f.close();
g.close();
return 0;
}