Pagini recente » Cod sursa (job #829242) | Cod sursa (job #2588975) | Cod sursa (job #1939247) | Cod sursa (job #911168) | Cod sursa (job #534762)
Cod sursa(job #534762)
#include<stdio.h>
#include<algorithm>
#define Nmax 100010
using namespace std;
struct oi { int D, val ; } v[Nmax];
int cmp( oi a, oi b )
{
return a.D < b.D ;
}
int h[Nmax],poz[Nmax];
int i,n,L,l,x,K,step,ld;
long long sol ;
void swap ( int i, int j )
{
poz[h[i]] = j ;
poz[h[j]] = i ;
int aux = h[i] ; h[i] = h[j] ; h[j] = aux ;
}
int pozmax ( int i )
{
int j = (i<<1) ;
if( j < L )
if( v[h[j+1]].val > v[h[j]].val ) return j + 1 ;
return j ;
}
void down ( int i )
{
if ( i <= (L>>1) )
{
int k = pozmax(i);
if( v[h[k]].val > v[h[i]].val )
{
swap(i,k);
down(k);
}
}
}
void up ( int i )
{
int j = (i>>1) ;
if( i > 1 )
{
if( v[h[i]].val > v[h[j]].val )
{
swap(i,j);
up(j);
}
}
}
void push ( int x )
{
h[++L] = x ;
poz[x] = L ;
up(L);
}
void pop ( int p )
{
swap(p,L);
poz[h[L]] = 0 ;
h[L] = 0 ; L--;
down(p);
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d %d %d",&n,&x,&l);
for( i = 1 ; i <= n ; i++ )
{
K++;
scanf("%d %d",&v[K].D,&v[K].val) ;
if( v[i].D > x ) { K--; continue ; }
v[K].D = 1 + ( x - v[K].D ) / l ;
if( v[K].D > ld ) ld = v[K].D ;
}
sort(v+1,v+K+1,cmp);
for( i = 1 ; i <= K ; i++ )
push(i);
i = 1 ;
for( step = 1 ; step <= ld ; step++ )
{
sol += (long long)v[h[1]].val;
pop(1);
for( ; v[i].D == step && i <= K ; i++ )
if( poz[i]) pop(poz[i]);
}
printf("%lld",sol);
return 0 ;
}