Pagini recente » Cod sursa (job #2042738) | Cod sursa (job #1771261) | Cod sursa (job #1314092) | Cod sursa (job #989049) | Cod sursa (job #933)
Cod sursa(job #933)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define nm 100100
void sort(int, int);
int part(int, int);
void hins(int);
void hdel();
int n, x, l, d[nm], a[nm], h[nm], sol;
int main()
{
int i, crt, tmp, x1, y1;
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
scanf("%d%d%d", &n, &x, &l);
for (i = 1; i <= n; ++i)
scanf("%d%d", &d[i], &a[i]);
srand(time(0));
for (i = 1; i <= 100000; ++i)
{
x1 = rand() % n + 1;
y1 = rand() % n + 1;
if (x1 != y1)
{
tmp = a[x1];
a[x1] = a[y1];
a[y1] = tmp;
tmp = d[x1];
d[x1] = d[y1];
d[y1] = tmp;
}
}
sort(1, n);
for (i = 1; i <= n; ++i)
if (d[i] > x)
d[i] = 0;
else
d[i] = (x - d[i]) / l + 1;
for (crt = d[1], i = 1; crt > 0; --crt)
{
for (; d[i] == crt; ++i)
hins(i);
if (h[0])
{
sol += a[h[1]];
hdel();
}
}
printf("%d\n", sol);
return 0;
}
void sort(int p, int r)
{
int q;
if (p < r)
{
q = part(p, r);
sort(p, q - 1);
sort(q + 1, r);
}
}
int part(int p, int r)
{
int i = p - 1, j, tmp;
for (j = p; j <= r; ++j)
if (d[j] <= d[r])
{
++i;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
tmp = d[i];
d[i] = d[j];
d[j] = tmp;
}
return i;
}
void hins(int x)
{
int crt, tmp;
h[++h[0]] = x;
crt = h[0];
while(crt > 1 && a[h[crt]] > a[h[crt / 2]])
{
tmp = h[crt];
h[crt] = h[crt / 2];
h[crt / 2] = tmp;
crt /= 2;
}
}
void hdel()
{
int crt, tmp, aux;
h[1] = h[h[0]--];
crt = 1;
if (crt * 2 + 1 > h[0] || a[h[crt * 2]] > a[h[crt * 2 + 1]])
aux = crt * 2;
else
aux = crt * 2 + 1;
while(crt * 2 <= h[0] && a[h[crt]] < a[h[aux]])
{
tmp = h[crt];
h[crt] = h[aux];
h[aux] = tmp;
crt = aux;
if (crt * 2 + 1 > h[0] || a[h[crt * 2]] > a[h[crt * 2 + 1]])
aux = crt * 2;
else
aux = crt * 2 + 1;
}
}