Cod sursa(job #1275130)

Utilizator vladrochianVlad Rochian vladrochian Data 24 noiembrie 2014 20:08:23
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

const int kMaxN = 100005;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

int N, X, L, S;
struct Sheep {
	int val, step;
	bool operator<(const Sheep &other) const {
		return step > other.step;
	}
} a[kMaxN];
priority_queue<int> Q;

int main() {
	fin >> N >> X >> L;
	for (int i = 0; i < N; ++i) {
		int dist;
		fin >> dist >> a[i].val;
		dist = X - dist + 1;
		a[i].step = dist / L + (dist % L ? 1 : 0);
	}
	sort(a, a + N);
	for (int step = a[0].step, i = 0; step && i < N; --step) {
		while (i < N && a[i].step == step)
			Q.push(a[i++].val);
		if (!Q.empty()) {
			S += Q.top();
			Q.pop();
		}
	}
	fout << S << "\n";
	return 0;
}