Pagini recente » Cod sursa (job #1492386) | Cod sursa (job #67077) | Cod sursa (job #777997) | Cod sursa (job #1934603) | Cod sursa (job #954)
Cod sursa(job #954)
#include <cstdio>
#include <algorithm>
using namespace std;
#define nm 100100
void hins(int);
void hdel();
struct elem
{
int d, c;
};
int cmp(struct elem a, struct elem b)
{
return a.d < b.d;
}
int n, x, l, h[nm];
long long sol;
elem a[nm];
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", &a[i].d, &a[i].c);
sort(a + 1, a + n + 1, cmp);
for (i = 1; i <= n; ++i)
if (a[i].d > x)
a[i].d = 0;
else
a[i].d = (x - a[i].d) / l + 1;
for (crt = a[1].d, i = 1; crt > 0; --crt)
{
for (; a[i].d == crt; ++i)
hins(i);
if (h[0])
{
sol = (long long)sol + a[h[1]].c;
hdel();
}
}
printf("%lld\n", sol);
return 0;
}
void hins(int x)
{
int crt, tmp;
h[++h[0]] = x;
crt = h[0];
while(crt > 1 && a[h[crt]].c > a[h[crt / 2]].c)
{
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]].c > a[h[crt * 2 + 1]].c)
aux = crt * 2;
else
aux = crt * 2 + 1;
while(crt * 2 <= h[0] && a[h[crt]].c < a[h[aux]].c)
{
tmp = h[crt];
h[crt] = h[aux];
h[aux] = tmp;
crt = aux;
if (crt * 2 + 1 > h[0] || a[h[crt * 2]].c > a[h[crt * 2 + 1]].c)
aux = crt * 2;
else
aux = crt * 2 + 1;
}
}