Cod sursa(job #956033)

Utilizator tudorv96Tudor Varan tudorv96 Data 2 iunie 2013 01:02:03
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

#define in "lupu.in"
#define out "lupu.out"
#define N 100005
#define hs H.size()-1

typedef pair <int, int> data;

vector <data> H;
int n, sol, X, l;

void insert(data v) {
	H.push_back (v);
	int k = hs;
	while (k / 2 > 0 && H[k] > H[k / 2]) {
		swap (H[k], H[k / 2]);
		k /= 2;
	}
}

void eject() {
	H[1] = H[hs];
	H.pop_back();
	unsigned k = 1, kk = 0;
	while (kk <= hs) {
		kk = k * 2;
		if (kk + 1 <= hs && H[kk] < H[kk + 1])
			kk++;
		if (kk <= hs && H[k] < H[kk]) {
			swap (H[k], H[kk]);
			k = kk;
		}
		else
			break;
	}
}

int main() {
	H.push_back (data(0,0));
	ifstream fin (in);
	fin >> n >> X >> l;
	for (int i = 0; i <= n; ++i) {
		int x, y;
		fin >> x >> y;
		x = (x + l - 1) / l;
		if (x <= X) 
		insert(data(x, y));
	}
	for (int i = (X + l - 1) / l; i >= 0; --i)
		if (hs) {
			sol += H[1].second;
			eject();
			//cout << i << " " << H[1].first << " " << H[1].second << "\n";
			while (hs && H[1].first >= i)
				eject();
		}
	ofstream fout (out);
	fout << sol;
	fout.close();
	return 0;
}