Cod sursa(job #1139020)

Utilizator cdt2014Cont de Teste cdt2014 Data 10 martie 2014 19:59:42
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;

class Lupu {
public:
	Lupu(vector< pair<int,int> > V, int X, int L) {
		for (size_t i=0; i<V.size(); ++i) {
			sheep.push_back(make_pair( 
						min(- (X-V[i].first) / L, 0),
						V[i].second)
			);
			// cout << sheep[sheep.size() - 1].first << " " << sheep[sheep.size() - 1].second << endl;
		}
	}

	long long solve() {
		sort(sheep.begin(), sheep.end());
		priority_queue<int> Q;

		long long total = 0;
		for (int t= -sheep[0].first, i=0; t >= 0; --t) {
			while (i<sheep.size() && sheep[i].first == -t) {
				Q.push(sheep[i].second);
				++ i;
			}
			int chosen = Q.top();
			// cout << "chose: " << chosen << endl;
			total += chosen;
			Q.pop();
		}

		return total;
	}
private:
	vector< pair<int,int> > sheep;
};

int main() {
	ifstream in("lupu.in");
	ofstream out("lupu.out");

	vector< pair<int,int> > V;
	int N, X, L;
	in >> N >> X >> L;
	while (N--) {
		int q, d;
		in >> d >> q;

		V.push_back(make_pair(d, q)); 
	}

	Lupu lup(V, X, L);
	out << lup.solve() << "\n";
	return 0;
}