Pagini recente » Cod sursa (job #1989655) | Cod sursa (job #1906094) | Cod sursa (job #2439423) | Cod sursa (job #2913434) | Cod sursa (job #5701)
Cod sursa(job #5701)
#include <cstdio>
#include <algorithm>
using namespace std;
#define FIN "lupu.in"
#define FOUT "lupu.out"
#define MAX 100050
#define pozMin 100040
struct oaie {
long l, d;
};
long X,L,N, ans;
long T[MAX], O[MAX];
oaie A[MAX];
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) {
scanf("%ld %ld", &A[i].d, &A[i].l);
O[i]=i;
for (T[i] = 0; T[i]*L+A[i].d<=X ; ++ T[i]);
}
fclose(stdout);
}
bool comp(const long &x, const long &y) {
return (T[x]>T[y]);
}
void solve() {
long i = 0, pos, ok;
oaie temp;
sort(O, O+N, comp);
pos=N-1;
for (i=0; pos>=0 || !H.comp(L*i); i++) {
for (ok = T[O[pos]]; T[O[pos]] == ok; --pos)
H.push(A[O[pos]].l, A[O[pos]].d);
// pos--;
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;
}