Pagini recente » Cod sursa (job #1102430) | Cod sursa (job #2700261) | Cod sursa (job #574630) | Cod sursa (job #2327833) | Cod sursa (job #330711)
Cod sursa(job #330711)
#include<stdio.h>
#define MAX_N 100000+1
long long int n,nn,x,l,k;
long long int sol;
long long int A[MAX_N],Heap[MAX_N];
long long int T_MAX = -1;
long long int T[MAX_N];
void read(),solve(),heapUp(long long int),heapDown(long long int),heapDown2(long long int);
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
read();
solve();
printf("%lld\n",sol);
fclose(stdin); fclose(stdout);
return 0;
}
void read()
{
long long int i;
scanf("%lld%lld%lld",&n,&x,&l);
T_MAX = x/l+1;
for(i = 1; i <= n; i++)
{
scanf("%lld %lld",&T[i],&A[i]);
if(T[i] <= x)
{
T[i] = (x-T[i])/l+1;
}
else
{
n--; i--;
}
}
nn = n;
for(i = nn/2; i >= 1; i--)
heapDown2(i);
while(nn > 2)
{
T[1] ^= T[nn] ^= T[1] ^= T[nn];
A[1] ^= A[nn] ^= A[1] ^= A[nn];
heapDown2(1);
nn--;
}
}
void solve()
{
long long int i;
long long int pos = n;
for(i = T_MAX; i >= 1; i--)
{
while(T[pos] == i)
{
Heap[++k] = A[pos];
heapUp(k);
pos--;
}
if(k)
{
sol+= Heap[1];
Heap[1] = Heap[k];
Heap[k--]=0;
heapDown(1);
}
}
}
void heapUp(long long int v)
{
long long int key = Heap[v];
while(v > 1 && key > Heap[v/2])
{
Heap[v/2] = Heap[v];
v/=2;
}
Heap[v] = key;
}
void heapDown(long long int v)
{
long long int w = v*2;
while(w <= k)
{
if(w+1 <= k && Heap[w+1] > Heap[w]) w++;
if(Heap[v] >= Heap[w]) return;
Heap[w] ^= Heap[v] ^= Heap[w] ^= Heap[v];
v = w;
w *= 2;
}
}
void heapDown2(long long int v)
{
long long int w = v*2;
while(w < nn)
{
if(w+1 < nn && T[w+1] > T[w]) w++;
if(T[v] >= T[w]) return;
T[w] ^= T[v] ^= T[w] ^= T[v];
A[w] ^= A[v] ^= A[w] ^= A[v];
v = w;
w *= 2;
}
}