Cod sursa(job #95529)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 29 octombrie 2007 12:27:04
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

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

int size = 0;
pair <int, int> H[N_MAX], vec[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 ((poz >> 1) >= 1 && H[poz].second > H[poz >> 1].second) {
		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(0, 0);

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

	while (((poz << 1) <= size || ((poz << 1) + 1) <= size) && (H[poz].second < H[poz << 1].second || H[poz].second < H[(poz << 1) + 1].second)) {

		if (H[poz << 1].second > H[(poz << 1) + 1].second) 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 cmp(pair <int, int> a, pair <int, int> b)
{
	return (a.first > b.first);
}

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

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

	scanf("%d %d %d\n", &N, &X, &L);
	for (i = 1; i <= N; i ++) {
		scanf("%d %d\n", &y, &l);
		vec[i] = make_pair((X - y) / L, l);
	}
	sort(vec + 1, vec + N + 1, cmp);
	
	int tmax = vec[1].first, poz = 1, rez = 0, j;		

	for (i = tmax; i >= 0; i --) {
		while (vec[poz].first == i && poz <= N) {
			push(i, vec[poz].second);
			poz ++;
		}
		
		rez += H[1].second;
		pop(1);
	}
	
	printf("%d\n", rez);
	
	return 0;
}