Pagini recente » Cod sursa (job #2986804) | Cod sursa (job #1781933) | Cod sursa (job #279841) | Cod sursa (job #1280426) | Cod sursa (job #14541)
Cod sursa(job #14541)
using namespace std;
#include <cstdio>
#include <algorithm>
#include <queue>
#define FIN "lupu.in"
#define FOUT "lupu.out"
#define NMAX 100001
int v[NMAX], N, X, L, tmax, dimheap;
struct lupi {int a, t;};
lupi l[NMAX];
int ord[NMAX];
int cmp (const int a, const int b)
{
return l[a].t > l[b].t;
}
void reconst_heap (int i)
{
int l, r, maxim;
l = (i<<1);
r = (i<<1) + 1;
if (l <= dimheap && v[l] > v[i])
maxim = l;
else
maxim = i;
if (r <= dimheap && v[r] > v[maxim])
maxim = r;
if (maxim != i)
{
v[i] ^= v[maxim];
v[maxim] ^= v[i];
v[i] ^= v[maxim];
reconst_heap (maxim);
}
}
int extr_max_heap ()
{
int max;
if (dimheap < 1)
return 0;
dimheap--;
max = v[1];
v[1] = v[dimheap + 1];
reconst_heap(1);
return max;
}
void insert_heap (int cheie)
{
int i;
dimheap++;
i = dimheap;
while (i > 1 && v[(i>>1)] < cheie)
{ v[i] = v[(i>>1)];
i >>= 1;
}
v[i] = cheie;
}
int
main ()
{
int i, P = 0, k, j, s = 0;
freopen (FIN, "rt", stdin);
freopen (FOUT, "wt", stdout);
scanf ("%d%d%d", &N, &X, &L);
scanf ("%d%d", &l[1].t, &l[1].a);
ord[1] = 1;
l[1].t = (X - l[1].t) / L;
if (tmax < l[1].t)
tmax = l[1].t;
for (i = 2; i <= N; i++)
{
scanf ("%d%d", &l[i].t, &l[i].a);
ord[i] = i;
l[i].t = (X - l[i].t) / L;
if (l[i].t > l[i-1].t) P = 1;
if (tmax < l[i].t)
tmax = l[i].t;
}
k = 1;
l[N+1].t = 100;
ord[N+1] = N+1;
if (P == 1)
sort (ord+1, ord+N+1, cmp);
for (j = tmax; j >= 0; j--)
{
if (l[ord[k]].t == j)
while (l[ord[k]].t == j)
{
insert_heap (l[ord[k]].a);
k++;
}
s += extr_max_heap ();
}
printf ("%d\n", s);
return 0;
}