Cod sursa(job #2286866)

Utilizator flibiaVisanu Cristian flibia Data 20 noiembrie 2018 21:54:59
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;

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

int n, vf;
ll x, l, ans, add, a, b, mx;
pair <ll, ll> st[100100];
set <pair <ll, ll> > h; 

int main() {
	in >> n >> x >> l;
	for (int i = 1; i <= n; i++) {
		in >> a >> b;
		ll can = (x - a) / l;
		if (can >= 0)
			st[++vf] = {-b, can};
		mx = max(mx, can);
	}
	sort(st + 1, st + vf + 1);
	h.insert({0, mx});
	for (int i = 1; i <= vf; i++) {
		if (h.size() == 0)
			break;
		ll v = st[i].se;
		if ((*h.begin()).fi > v)
			continue;
		auto it = h.upper_bound({v, 0});
		it--;
		auto seg = *it;
		h.erase(it);
		ans -= st[i].fi;
		if (v > seg.fi)
			h.insert({seg.fi, v - 1});
		if (v < seg.se)
			h.insert({v + 1, seg.se});
	}
	out << ans;
	return 0;
}