Pagini recente » Cod sursa (job #1022561) | Cod sursa (job #2713852) | Cod sursa (job #685059) | Cod sursa (job #2374503) | Cod sursa (job #1839804)
#include <cstdio>
#include <algorithm>
using namespace std;
int NR, Tmax, n, x, l, d, a[100005], T[100005], pos[100005], Heap[100005];
inline bool cmp(int x, int y){
return T[x] < T[y];
}
inline void push(int x){
while(x / 2 && a[Heap[x]] > a[Heap[x / 2]]){
int aux = Heap[x];
Heap[x] = Heap[x / 2];
Heap[x / 2] = aux;
}
}
inline void pop(int x){
int y = 0;
while(x != y){
y = x;
if(y * 2 <= NR && a[Heap[x]] < a[Heap[y * 2]]) x = y * 2;
if(y * 2 + 1 <= NR && a[Heap[x]] < a[Heap[y * 2 + 1]]) x = y * 2;
int aux = Heap[x];
Heap[x] = Heap[y];
Heap[y] = aux;
}
}
int main()
{
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
scanf("%d%d%d", &n, &x, &l);
for(int i = 1; i <= n ; ++i){
scanf("%d%d", &d, &a[i]);
if(d > x)
T[i] = 0;
else
T[i] = 1 + (x - d) / l;
if(T[i] > Tmax)
Tmax = T[i];
pos[i] = i;
}
sort(pos + 1, pos + n + 1, cmp);
int L = n, Sol = 0;
for(int j = Tmax; j >= 1 ; --j){
if(T[pos[L]] == j){
for(L; T[pos[L]] == j ; --L){
++NR;
Heap[NR] = pos[L];
push(NR);
}
}
if(NR == 0) continue;
Sol += a[Heap[1]];
a[Heap[1]] = -1;
push(1);
Heap[1] = Heap[NR--];
pop(1);
}
printf("%d", Sol);
return 0;
}