Pagini recente » Cod sursa (job #1897366) | Cod sursa (job #1551667) | Cod sursa (job #1112255) | Cod sursa (job #1971709) | Cod sursa (job #73134)
Cod sursa(job #73134)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct oaie {
int d,l;
bool operator< ( oaie a ) { return l < a.l; };
bool operator> ( oaie a ) { return l > a.l; };
oaie& operator= ( oaie a ) { d = a.d; l = a.l; return *this;}
};
template <class tip> class heap {
vector<tip> v;
void replace ( tip& a, tip& b ) { tip temp = a; a = b; b = temp; };
public:
heap() {};
~heap() {};
void push ( tip x ) {
v.push_back(x);
for (int cur = v.size() - 1; cur > 0 && v[cur / 2] < v[cur]; cur /= 2) {
replace(v[cur/2],v[cur]);
}
};
tip& front() { return v[0]; };
void pop() {
int cur = v.size() - 1;
replace(v[0],v[cur]);
v.pop_back();
cur = 0;
for (;;) {
bool st = (2*cur < ((int) v.size()) && v[2*cur] > v[cur]);
bool dr = (2*cur+1 < ((int) v.size()) && v[2*cur+1] > v[cur]);
if (st && dr) {
if (v[2*cur] > v[2*cur+1])
replace(v[cur],v[2*cur]); else
replace(v[cur],v[2*cur+1]);
} else
if (st) replace(v[cur],v[2*cur]); else
if (dr) replace(v[cur],v[2*cur+1]); else
break;
}
};
};
const int N = 100000;
int n,dm,dr;
oaie o[N];
bool compdd ( oaie a, oaie b ) { return a.d > b.d; };
int main() {
freopen("lupu.in","rt",stdin);
freopen("lupu.out","wt",stdout);
scanf("%d %d %d",&n,&dm,&dr);
for (int i = 0; i<n; ++i) {
scanf("%d %d",&o[i].d,&o[i].l);
o[i].d = (dm - o[i].d)/dr + 1;
}
sort(o,o+n,compdd);
heap<oaie> H;
int r = 0;
for (int i = 0; i<n; ++i) {
H.push(o[i]);
if(o[i].d != o[i+1].d) {
r += (H.front()).l;
H.pop();
}
}
printf("%d\n",r);
return 0;
}