Pagini recente » Cod sursa (job #2147125) | Cod sursa (job #534529) | Cod sursa (job #1787319) | Cod sursa (job #2561054) | Cod sursa (job #73131)
Cod sursa(job #73131)
#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; };
};
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 < v.size() && v[2*cur] > v[cur]);
bool dr = (2*cur+1 < 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);
freopen("lupu.err","wt",stderr);
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;
}