Pagini recente » Cod sursa (job #1626387) | Cod sursa (job #426315) | Cod sursa (job #2767695) | Cod sursa (job #1103351) | Cod sursa (job #330550)
Cod sursa(job #330550)
#include<stdio.h>
#define MAX_N 100000+1
int n,x,l,k,sol;
int T[MAX_N],D[MAX_N],A[MAX_N],Heap[MAX_N];
int T_MAX = -1;
void read(),solve(),heapUp(int),heapDown(int);
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
read();
solve();
printf("%d\n",sol);
fclose(stdin); fclose(stdout);
return 0;
}
void read()
{
scanf("%d%d%d",&n,&x,&l);
for(int i = 0; i < n; i++)
{
scanf("%d %d",&D[i],&A[i]);
T[i] = (x-D[i])/l;
T_MAX = T_MAX > T[i] ? T_MAX : T[i];
}
}
void solve()
{
int i,j;
for(i = 1; i <= T_MAX; i++)
{
for(j = 0; j < n; j++)
{
if(T[j] == i)
{
Heap[++k] = A[j];
heapUp(k);
}
}
sol += Heap[1];
Heap[1] = Heap[--k];
heapDown(1);
}
}
void heapUp(int v)
{
int key = Heap[v];
while(v && key > Heap[v/2])
{
Heap[v/2] = Heap[v];
v/=2;
}
Heap[v] = key;
}
void heapDown(int v)
{
int w = v*2;
while(v <= 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;
}
}