Cod sursa(job #95995)

Utilizator andrei.12Andrei Parvu andrei.12 Data 30 octombrie 2007 22:09:47
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<stdio.h>
#include<stdlib.h>
#define infinit 2000000000
#define lg 10005
int n, ll, x, di, p, a, i, j, s, * d[lg], * ind[lg], max, l, nr[lg], gs[lg], viz[lg];
long long rezultat;
struct heap{
	int v, in;
};
heap hp[100005];
int gsnod(int i){
	if (2*i < n){
		if (hp[2*i].v < hp[2*i+1].v)
			return 2*i;
		return 2*i+1;
	}
	return 2*i;
}
void arj(int i){
	int nxt = gsnod(i), aux;
	if (i <= n/2)
		if (hp[i].v < hp[nxt].v){
			aux = hp[i].v;
			hp[i].v = hp[nxt].v;
			hp[nxt].v = aux;
			aux = hp[i].in;
			hp[i].in = hp[nxt].in;
			hp[nxt].in = aux;
			gs[hp[i].in] = i;
			gs[hp[nxt].in] = nxt;
			arj(nxt);
		}
}
int main()
{
	freopen("lupu.in", "rt", stdin);
	freopen("lupu.out", "wt", stdout);
	scanf("%d%d%d", &n, &x, &ll);
	// x - distanta maxima
	for (i=1; i<=n; i++){
		scanf("%d%d", &di, &a);
		// di - distanta
		l = (x-di) / ll +1;
		if (l){
			nr[l] ++;
			d[l] = (int *)realloc(d[l], (nr[l]+1)*sizeof(int));
			d[l][nr[l]] = a;
			ind[l] = (int *)realloc(ind[l], (nr[l]+1)*sizeof(int));
			ind[l][nr[l]] = i;
			if (l > max)
				max = l;
		}
		hp[i].v = a;
		hp[i].in = i;
	}
	for (i=n/2; i; i--)
		arj(i);
	for (i=1; i<=max; i++){
		if (nr[i]){
			s = 0;
			for (j=1; j<=nr[i]; j++){
				if (d[i][j] > s && !viz[ind[i][j]])
					s = d[i][j];
				p = gs[ind[i][j]];
				hp[p].v = infinit;
				arj(p);
			}
			rezultat += s;
		}
		else{
			rezultat += hp[1].v;
			hp[1].v = infinit;
			viz[hp[1].in] = 1;
			arj(1);
		}
	}
	printf("%lld\n", rezultat);
	fclose(stdin);
	fclose(stdout);
	return 0;
}