Cod sursa(job #954)

Utilizator sims_glAlexandru Simion sims_gl Data 12 decembrie 2006 12:04:15
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#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;
    }
}