Cod sursa(job #486600)

Utilizator Addy.Adrian Draghici Addy. Data 22 septembrie 2010 09:01:56
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 1000050;

struct sheep {
	int t, c;
} V[NMAX];

int H[NMAX], N, n, x, d, l, c, t, i, p, tmax;
long long cst;

int cmp (sheep a, sheep b) {
	return a.t > b.t;
}

void up_heap (int k) {
	
	int t, c, aux;
	
	c = k, t = c >> 1;
	while (t > 0 && H[c] > H[t]) {
		aux = H[c], H[c] = H[t], H[t] = aux;
		
		c = t, t = c >> 1;
	}
}

void down_heap (int k) {
	
	int t, c, aux;
	
	t = k, c = t << 1;
	if (c < N && H[c+1] > H[c]) c++;
	
	while (c <= N && H[c] > H[t]) {
		aux = H[c], H[c] = H[t], H[t] = aux;
		
		t = c, c = t << 1;
		if (c < N && H[c+1] > H[c]) c++;
	}
}

int main () {
	
	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, &c);
		V[i].t = (x - d) / l + 1;
		V[i].c = c;
		
		if (V[i].t > tmax) tmax = V[i].t;
	}
	
	sort (V + 1, V + 1 + n, cmp);
	
	for (i = tmax, p = 1; i >= 1 && p <= n; i--) {
		while (V[p].t == i && p <= n) {
			N++, H[N] = V[p++].c;
			up_heap (N);
		}
		
		if (N >= 1) {
			cst += (long long) H[1];
			H[1] = H[N], N--; down_heap (1);
		}
	}
	
	printf ("%lld", cst);
	
	return 0;
}