Pagini recente » Cod sursa (job #2679553) | Cod sursa (job #423959) | Cod sursa (job #718149) | Cod sursa (job #2624384) | Cod sursa (job #400910)
Cod sursa(job #400910)
#include<fstream>
#include<algorithm>
#define inf "lupu.in"
#define outf "lupu.out"
#define NMax 100010
using namespace std;
fstream f(inf,ios::in),g(outf,ios::out);
int N,X,L;
int d[NMax],a[NMax];
typedef int Heap[NMax];
Heap H;
int hdim;
struct elem
{
int t;
int l;
};
elem v[NMax];
void read()
{
f>>N>>X>>L;
for(int i=1;i<=N;i++)
{
f>>d[i]>>a[i];
v[i].t = ( (X-d[i])/L ) + 1 ;
v[i].l = i;
}
}
bool rule(elem a,elem b)
{
if( a.t < b.t ) return false;
return true;
}
void upheap(int nod)
{
int s;
while( nod>1 )
{
s= (nod>>1) ;
if( a[ H[s] ] < a[ H[nod] ] )
{
swap( H[s], H[nod] );
nod=s;
}
else break;
}
}
void downheap(int nod)
{
int f;
while( true )
{
f= (nod<<1) ;
if( f<=hdim )
{
if( f+1<=hdim && a[ H[f+1] ]>a[ H[f] ] ) ++f ;
if( a[ H[f] ] > a[ H[nod] ] )
{
swap( H[f], H[nod] );
nod=f;
}
else break;
}
else break;
}
}
void solve()
{
int j=1;
int s=0;
sort(v+1, v+N+1, rule);
for(int i=v[1].t ; i>=1; --i)
{
while( v[j].t == i && j<=N)
{
++hdim;
H[hdim] = v[j].l ;
upheap( hdim );
++j;
}
if( hdim )
{
s+= a [ H[1] ];
H[1]=H[hdim];
--hdim;
downheap( 1 );
}
}
g<< s ;
}
int main()
{
read();
solve();
f.close();
g.close();
return 0;
}