Pagini recente » Cod sursa (job #2901317) | Cod sursa (job #1186389) | Cod sursa (job #2724274) | Cod sursa (job #1903804) | Cod sursa (job #2839783)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
struct oaie {
int d;
int a;
bool operator<(const oaie& o) const {
return d > o.d;
}
};
oaie v[N];
class Heap {
private:
vector<int> h;
void up(int nod) {
while (nod > 1 && v[h[nod]].a < v[h[nod / 2]].a) {
swap(h[nod], h[nod / 2]);
nod /= 2;
}
}
void down(int nod) {
while (nod * 2 < h.size()) {
int 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(int x) {
h.push_back(x);
up(h.size() - 1);
}
int 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");
int n, x, l;
cin >> n >> x >> l;
for (int i = 0; i < n; ++i)
cin >> v[i].d >> v[i].a;
cin.close();
sort(v, v + n);
Heap h;
long long ans = 0;
for (int i = 0; i < n; ++i) {
if (v[i].d <= x) {
h.push(i);
ans += v[i].a;
x -= l;
} else {
int poz = h.top();
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;
}