Cod sursa(job #929)

Utilizator sims_glAlexandru Simion sims_gl Data 12 decembrie 2006 09:09:49
Problema Lupul Urias si Rau Scor 64
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <stdio.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], v[nm], h[nm], sol;

int main()
{
	int i, crt;

	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]);

    sort(1, n);
    
    for (i = 1; i <= n; ++i)
    	if (d[i] > x)
        	v[i] = 0;
        else
        	v[i] = (x - d[i]) / l + 1;

    for (crt = v[1], i = 1; crt > 0; --crt)
    {
    	for (; v[i] == crt; ++i)
        	hins(i);

        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;
    }
}