Cod sursa(job #96630)

Utilizator andrei.12Andrei Parvu andrei.12 Data 2 noiembrie 2007 15:18:20
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<stdio.h>
#include<stdlib.h>
#define infinit -2000000000
#define lg 100005
int n, x, l, *dist[lg], oi, timp, gs[lg], r, ds, i, nr[lg];
long long raspuns;
struct citire{
	int v, d;
};
citire v[lg];
struct heap{
	int v, in;
};
heap hp[lg];
int gsnod(int i){
	if (2*i < n){
		if (hp[2*i].v <= hp[2*i+1].v)
			return 2*i+1;
		return 2*i;
	}
	return 2*i;
}
void arj(int i){
	int nxt = gsnod(i), aux;
	if (2*i <= n)
		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[nxt].in] = nxt;
			gs[hp[i].in] = i;
			arj(nxt);
		}
}
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 mareste
	for (i=1; i<=n; i++){
		scanf("%d%d", &v[i].d, &v[i].v);
		if (v[i].d <= x)
			oi ++;
	}
	for (i=1; i<=n; i++)
		if (v[i].d <= x){
			hp[i].v = v[i].v;
			hp[i].in = i;
			ds = (x-v[i].d) / l + 1;
			nr[ds] ++;
			dist[ds] = (int *)realloc(dist[ds], (nr[ds]+1)*sizeof(int));
			dist[ds][nr[ds]] = i;
		}
	for (i=oi/2; i; i--)
		arj(i);
	timp = 1;
	while (oi){
		raspuns += hp[1].v;
		hp[1].v = infinit;
		arj(1);
		for (i=1; i<=nr[timp]; i++){
			r = gs[dist[timp][i]];
			hp[r].v = infinit;
			arj(r);
		}
		oi -= nr[timp];
		timp ++;
	}
	printf("%lld\n", raspuns);
	return 0;

}