Pagini recente » Borderou de evaluare (job #2728551) | Cod sursa (job #2671860) | Borderou de evaluare (job #2686895) | Cod sursa (job #2670518) | Cod sursa (job #144050)
Cod sursa(job #144050)
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
struct oaie { int w,d; };
const int N = 100000;
int n;
oaie o[N];
bool sort_cmp ( const oaie &a, const oaie &b ) { return (a.d > b.d); };
class set_cmp {
public:
bool operator() ( const oaie &a, const oaie &b ) { return (a.w > b.w); };
};
template <class T, class cmp> class heap {
T* v;
int n;
int alloc;
void extend() {
int new_alloc = alloc * 2;
T* new_v = (T*)malloc(sizeof(T)*alloc);
memcpy(new_v,v,n*sizeof(T));
free(v);
v = new_v;
alloc = new_alloc;
};
public:
heap() {
alloc = 2;
v = (T*)malloc(sizeof(T)*2);
};
~heap() {};
void insert ( T x ) {
if ( n == alloc ) extend();
++n;
v[n] = x;
for (int c = n; c > 0 && v[c/2] < v[c]; ) {
T tmp = v[c];
v[c] = v[c/2];
v[c/2] = tmp;
c /= 2;
}
};
T* top() { return v; };
void pop() {
T tmp = v[0];
v[0] = v[n];
v[n] = tmp;
--n;
for (int c = 0; ; ) {
if (cmp(v[c],v[c*2])) {
if (!cmp(v[c*2],v[c*2+1])) {
tmp = v[c];
v[c] = v[c*2];
v[c*2] = tmp;
} else {
tmp = v[c];
v[c] = v[c*2+1];
v[c*2+1] = tmp;
}
} else
if (!cmp(v[c],v[c*2+1])) {
tmp = v[c];
v[c] = v[c*2+1];
v[c*2+1] = tmp;
} else {
break;
}
}
};
};
int main() {
freopen("lupu.in","rt",stdin);
freopen("lupu.out","wt",stdout);
int x, dp;
scanf("%d %d %d",&n,&x,&dp);
for (int i = 0; i < n; ++i) {
scanf("%d %d",&o[i].d,&o[i].w);
o[i].d = ((x-o[i].d)/dp)+1;
}
sort(o,o+n,sort_cmp);
long long r = 0;
heap<oaie,set_cmp> heap;
for (int t = o[0].d, i = 0; t; --t) {
for (; i < n && o[i].d == t; heap.insert(o[i]), ++i);
if (!heap.empty()) {
r += (long long)heap.top()->w;
heap.pop();
}
}
printf("%lld\n",r);
return 0;
}