Cod sursa(job #1275601)

Utilizator vladrochianVlad Rochian vladrochian Data 25 noiembrie 2014 13:32:38
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <set>
#include <algorithm>
using namespace std;

const int kMaxN = 100005;

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

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

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);
		step_max = max(step_max, a[i].step);
	}
	sort(a, a + N);
	for (int i = 1; i <= step_max; ++i)
		available.insert(i);
	for (int i = 0; i < N && !available.empty(); ++i) {
		auto it = available.lower_bound(a[i].step);
		if (it != available.end()) {
			S += a[i].val;
			available.erase(it);
		}
	}
	fout << S << "\n";
	return 0;
}