Cod sursa(job #97288)

Utilizator andrei.12Andrei Parvu andrei.12 Data 6 noiembrie 2007 10:37:13
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 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, rezultat[100], s[100], k;
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);
		}
}
void add(int a[], int b[]){
	int i, r = 0;
	for (i=1; i<=a[0] || i<=b[0] || r; i ++, r /= 10)
		a[i] = (r += a[i]+b[i]) % 10;
	a[0] = i-1;
}
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);
		}
		k = hp[1];
		while (k){
			s[++s[0]] = k % 10;
			k /= 10;
		}
		add(rezultat, s);
		for (j=s[0]; j>=0; j--)
			s[j] = 0;
		hp[1] = infinit;
		arj(1);
	}
	for (i=rezultat[0]; i; i--)
		printf("%d", rezultat[i]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}