Cod sursa(job #933)

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