Pagini recente » Cod sursa (job #2528627) | Cod sursa (job #1941765) | Cod sursa (job #2626438) | Cod sursa (job #1385954) | Cod sursa (job #2839790)
#include <fstream>
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;
const ll N = 1e5 + 5;
struct oaie {
ll d;
ll a;
bool operator<(const oaie& o) const {
return d > o.d;
}
};
oaie v[N];
class Heap {
private:
vector<ll> h;
void up(ll nod) {
while (nod > 1 && v[h[nod]].a < v[h[nod / 2]].a) {
swap(h[nod], h[nod / 2]);
nod /= 2;
}
}
void down(ll nod) {
while (nod * 2 < h.size()) {
ll fiu = nod * 2;
if (fiu + 1 < h.size() && v[h[fiu + 1]].a < v[h[fiu]].a)
fiu = fiu + 1;
if (v[h[nod]].a <= v[h[fiu]].a)
break;
swap(h[nod], h[fiu]);
nod = fiu;
}
}
public:
Heap() {
h.push_back(0);
}
void push(ll x) {
h.push_back(x);
up(h.size() - 1);
}
ll top() {
if (empty())
return -1;
return h[1];
}
void pop() {
h[1] = h.back();
h.pop_back();
down(1);
}
bool empty() {
return h.size() <= 1;
}
};
int main() {
ifstream cin("lupu.in");
ofstream cout("lupu.out");
ll n, x, l;
cin >> n >> x >> l;
for (ll i = 0; i < n; ++i)
cin >> v[i].d >> v[i].a;
cin.close();
sort(v, v + n);
Heap h;
ll ans = 0;
for (ll i = 0; i < n; ++i) {
if (v[i].d <= x) {
h.push(i);
ans += v[i].a;
x -= l;
} else {
ll poz = h.top();
if (poz == -1)
continue;
if (v[poz].a < v[i].a) {
ans += v[i].a - v[poz].a;
h.pop();
h.push(i);
}
}
}
cout << ans << "\n";
cout.close();
return 0;
}