Cod sursa(job #97289)

Utilizator andrei.12Andrei Parvu andrei.12 Data 6 noiembrie 2007 10:39:43
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>
#include<stdlib.h>
#define infinit -2000000000
#define lg 100005
int hp[lg], *d[lg], i, n, x, l, ind, j, v[lg], dist, ds, nr[lg], max;
long long rezultat;
int gsnod(int i){
	if (2*i < ind){
		if (hp[2*i] > hp[2*i+1])
			return 2*i;
		return 2*i+1;
	}
	return 2*i;
}
void arj(int i){
	int aux, nxt = gsnod(i);
	if (2*i <= ind)
		if (hp[i] < hp[nxt]){
			aux = hp[i], hp[i] = hp[nxt], hp[nxt] = aux;
			arj(nxt);
		}
}
void crr(int i){
	int aux;
	if (i > 1)
		if (hp[i] > hp[i/2]){
			aux = hp[i], hp[i] = hp[i/2], hp[i/2] = aux;
			crr(i/2);
		}
}
int main()
{
	freopen("lupu.in", "rt", stdin);
	freopen("lupu.out", "wt", stdout);
	scanf("%d%d%d", &n, &x, &l);
	//x - distanta maxima
	//l - cu cat se deplaseaza
	for (i=1; i<=n; i++){
		scanf("%d%d", &dist, &v[i]);
		ds = (x-dist) / l + 1;
		if (ds >= 1){
			nr[ds] ++;
			d[ds] = (int *)realloc(d[ds], (nr[ds]+1)*sizeof(int));
			d[ds][nr[ds]] = i;
			if (ds > max)
				max = ds;
		}
	}
	ind = 1;
	for (i=max; i; i--){
		for (j=1; j<=nr[i]; j ++){
			hp[++ind] = v[d[i][j]];
			crr(ind);
		}
		if (hp[1] != infinit){
			rezultat += hp[1];
			hp[1] = infinit;
			arj(1);
		}
	}
	printf("%lld\n", rezultat);
	fclose(stdin);
	fclose(stdout);
	return 0;
}