Pagini recente » Cod sursa (job #2952240) | Cod sursa (job #248188) | Cod sursa (job #968305) | Cod sursa (job #2269003) | Cod sursa (job #2767307)
#include <bits/stdc++.h>
#define NMAX 1000003
using namespace std;
bool bigger(int a,int b) {
return a > b;
}
template <typename T>
class heap {
private:
vector<T> t;
// pereche (prioritate, pufosenie);
bool (*comp)(T a, T b);
void upHeap(int idx) {
while(idx > 1 && comp(t[idx], t[idx/2]) ) {
swap(t[idx/2], t[idx]);
idx = idx/2;
}
}
void downHeap(int idx) {
// recursiv
int best = idx;
if(2 * idx <= size() && comp(t[2 * idx], t[best]) ) {
best = 2 * idx;
}
if(2 * idx + 1 <= size() && comp(t[2 * idx + 1],t[best] )) {
best = 2 * idx + 1;
}
if(best != idx) {
swap(t[best], t[idx]);
downHeap(best);
}
}
public:
int size() {
return (int)t.size() - 1;
}
heap(bool (* f)(T a, T b) ) {
t.resize(1);
comp = f;
}
void insert(T val) {
t.push_back(val);
upHeap(size());
}
void pop() {
swap(t[1], t[size()]);
t.pop_back();
downHeap(1);
}
T top() {
return t[1];
}
};
int n, x, l;
vector<pair<int,int> > v;
int main() {
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d %d %d",&n,&x,&l);
int hmax = 0;
for(int i = 1; i <= n; i++) {
int a, b;
scanf("%d %d",&a,&b);
if(a <= x) {
v.push_back({(x - a)/l, b});
hmax = max(hmax, (x - a)/l);
}
}
sort(v.rbegin(), v.rend());
heap<int> h(bigger);
int sol = 0;
int idx = 0;
for(int i = hmax; i >= 0; i--) {
while(idx < v.size() && v[idx].first == i) {
h.insert(v[idx++].second);
}
if(h.size() > 0) {
sol += h.top();
h.pop();
}
}
printf("%d",sol);
return 0;
}