Pagini recente » Cod sursa (job #108219) | Cod sursa (job #2502365) | Cod sursa (job #2691249) | Cod sursa (job #1451135) | Cod sursa (job #5697)
Cod sursa(job #5697)
#include <cstdio>
#define FIN "lupu.in"
#define FOUT "lupu.out"
#define MAX 100050
#define pozMin 100040
struct oaie {
long l, d;
};
long X,L,N, ans;
class heap {
private:
oaie H[MAX];
long Nh;
inline long t(long x) {
return (x-1) / 2;
}
inline long fs(long x) {
return (x*2) + 1;
}
inline long fd(long x) {
return (x*2) + 2;
}
inline void swap(long p1, long p2) {
oaie aux = H[p1]; H[p1] = H[p2]; H[p2] = aux;
}
public:
heap() {
Nh=0;
H[pozMin].l = -1;
}
bool empty() {
return (Nh==0);
}
bool comp(long offset) {
return H[0].d + offset > X;
}
void push(long l, long d) {
oaie temp; long i;
temp.l = l; temp.d = d;
H[Nh++] = temp;
// heapUp
for (i=Nh-1; i && H[t(i)].l < H[i].l; i=t(i))
swap(i, t(i));
}
oaie pop() {
oaie temp = H[0];
long i, p, f;
// heapDown
H[0] = H[--Nh];
for ( i=0; fs(i)<Nh &&
H[(
p = ( H[fs(i)].l>H[ f = (fd(i)<=Nh ? fd(i) : pozMin) ].l || (H[fs(i)].l == H[f].l && H[fs(i)].d > H[f].d) )
? fs(i) : fd(i)
)
].l > H[i].l ;
i=p )
swap(p, i);
return temp;
}
} H;
void read_data() {
long i;
freopen(FIN, "r", stdin);
scanf("%ld %ld %ld", &N, &X, &L);
for (i=0; i<N; ++i) {
long l,d;
scanf("%ld %ld", &d, &l);
H.push(l,d);
}
fclose(stdout);
}
void solve() {
long i = 0;
oaie temp;
for (i=0; !H.empty(); i++) {
while ( H.comp(L*i) && !H.empty() )
H.pop();
if ( !H.empty() ) {
temp = H.pop();
ans += temp.l;
}
}
}
void write_answer() {
freopen(FOUT, "w", stdout);
printf("%ld\n", ans);
fclose(stdout);
}
int main() {
read_data();
solve();
write_answer();
return 0;
}