Pagini recente » Cod sursa (job #239372) | Cod sursa (job #2232118) | Cod sursa (job #1664366) | Cod sursa (job #758042) | Cod sursa (job #1499538)
#include<cstdio>
#include<algorithm>
#define DIM 100001
using namespace std;
int N, X, L, NR, Time;
int w[DIM + 1], Heap[DIM + 1];
long long sol;
void percolate(int);
void sift(int);
struct vec {int x, y;} v[DIM + 1];
inline bool comp(vec a, vec b)
{
return a.x > b.x;
}
void change(int i, int j)
{
int aux = Heap[i];
Heap[i] = Heap[j];
Heap[j] = aux;
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int i;
scanf("%d%d%d", &N, &X, &L);
for (i = 1; i <= N; i++)
{
scanf("%d%d", &v[i].x, &v[i].y);
w[i] = i;
}
sort(v + 1, v + N + 1, comp);
for (i = 1; i <= N; i++)
{
if (X >= Time * L + v[w[i]].x)
{
Heap[++NR] = v[w[i]].y;
percolate(NR);
Time++;
}
else
{
if (Heap[1] < v[w[i]].y)
{
Heap[1] = v[w[i]].y;
sift(1);
}
}
}
for (i = 1; i <= NR; i++)
sol += 1LL * Heap[i];
printf("%ld", sol);
}
void percolate(int i)
{
while (i >= 2 && Heap[i] < Heap[i / 2])
{
change(i, i / 2);
i = i / 2;
}
}
void sift(int i)
{
int good = i;
if (2 * i <= NR && Heap[good] > Heap[2 * i])
good = 2 * i;
if (2 * i + 1 <= NR && Heap[good] > Heap[2 * i + 1])
good = 2 * i + 1;
if (good != i)
{
change(good, i);
sift(good);
}
}