Pagini recente » Cod sursa (job #2098635) | Cod sursa (job #1834942) | Cod sursa (job #1606524) | Cod sursa (job #2397424) | Cod sursa (job #2539956)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
#define nmax 100001
int n, x, l, p, h[nmax], total;
inline int father(int nod) { return nod/2; }
inline int left_son(int nod) { return nod*2; }
inline int right_son(int nod) { return nod*2+1; }
struct oaie {
int dist, lana;
} a[nmax];
bool mycmp(oaie a, oaie b) {
return a.dist > b.dist;
}
void sift(int n, int nod) {
int son;
do {
son = 0;
if (left_son(nod) <= p) {
son = left_son(nod);
if (right_son(nod) <= p && h[right_son(nod)] > h[son])
son = right_son(nod);
if (h[son] <= h[nod]) son = 0;
}
if (son) {
swap(h[nod], h[son]);
nod = son;
}
} while (son);
}
void percolate(int n, int nod) {
int key = h[nod];
while (nod > 1 && key > h[father(nod)]) {
h[nod] = h[father(nod)];
nod = father(nod);
}
h[nod] = key;
}
void cut(int &p, int nod) {
h[nod] = h[p];
--p;
if (nod > 1 && h[nod] > h[father(nod)]) percolate(p,nod);
else sift(p,nod);
}
int main()
{
f >> n >> x >> l;
for (int i = 1; i <= n; ++i) {
f >> a[i].dist >> a[i].lana;
//if (a[i].dist > x) a[i].dist = a[i].lana = 0, --i, --n;
a[i].dist = (x - a[i].dist) / l;
}
sort(a+1, a+n+1, mycmp);
/*for (int i = 1; i <= n; ++i) {
g << a[i].dist << ' ' << a[i].lana << '\n';
}*/
int j = 1;
for (int i = x/l; i >= 0; --i) {
while (a[j].dist >= i && j <= n) {
h[++p] = a[j].lana;
percolate(p,p);
++j;
}
total += h[1];
cut(p,1);
}
g << total << '\n';
return 0;
}