Cod sursa(job #95484)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 28 octombrie 2007 21:53:16
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>
#include <vector>

using namespace std;

const int N_MAX = 100010;
const int INF = 2000000000;

int size;
pair <int, int> H[N_MAX];

void push(int t, int l)
{
	pair <int, int> kkt, aux;
	kkt = make_pair(t, l);

	H[++ size] = kkt;
	int poz = size;

	while (H[poz].first < H[poz >> 1].first) {
		aux = H[poz >> 1];
		H[poz >> 1] = H[poz];
		H[poz] = aux;

		poz >>= 1;
	}
}

void pop(int poz)
{
	H[poz] = H[size];
	H[size] = make_pair(INF, INF);

	size --;
	int sch;
	pair <int, int> aux;

	while (H[poz] > H[poz << 1] || H[poz] > H[(poz << 1) + 1]) {

		if (H[poz << 1] < H[(poz << 1) + 1]) sch = poz << 1;
		else sch = (poz << 1) + 1;

//		if (kkt == 1) printf("%d\n", sch);

		aux = H[poz];
		H[poz] = H[sch];
		H[sch] = aux;

		poz = sch;
	}
//	if (kkt == 1) printf("\n");
}

int main()
{
	freopen("lupu.in", "r", stdin);
#ifndef _SCREEN_
	freopen("lupu.out", "w", stdout);
#endif

	int N, X, L, i, y, l;

	for (i = 1; i <= 5000; i ++) {
		H[i] = make_pair(INF, INF);
	}

	scanf("%d %d %d\n", &N, &X, &L);
	for (i = 1; i <= N; i ++) {
		scanf("%d %d\n", &y, &l);

		push((X - y) / L, l);
	}

	int last = H[1].first, MAX = H[1].second, rez = 0;
	pop(1);

	while (size) {

//		printf("%d %d\n", H[1].first, H[1].second);

		if (H[1].first != last) {
			rez += MAX;
			MAX = H[1].second;
			last = H[1].first;
		} else {
			if (H[1].second > MAX) MAX = H[1].second;
		}

		pop(1);

	}
	rez += MAX;

	printf("%d\n", rez);

	return 0;
}