Pagini recente » Cod sursa (job #137583) | Cod sursa (job #1785848) | Cod sursa (job #806972) | Cod sursa (job #1784492) | Cod sursa (job #490376)
Cod sursa(job #490376)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define DIM 100001
struct oaie {
int D, L, T;
};
oaie A[DIM];
int N, X, L, NH, H[DIM];
long long Lana;
int cmp (oaie a, oaie b) {
return a.T > b.T;
}
void cit () {
scanf ("%d%d%d", &N, &X, &L);
for (int i=1; i<=N; ++i) {
scanf ("%d%d", &A[i].D, &A[i].L);
A[i].T = (X - A[i].D) / L + 1;
}
}
void heap_u () {
int poz = NH;
while (poz/2 >= 1 && H[poz] > H[poz/2]) {
swap (H[poz/2], H[poz]);
poz = poz/2;
}
}
void heap_d () {
int poz = 1;
while (poz*2 <= NH) {
poz = poz*2;
if (poz+1 <= NH && H[poz] < H[poz+1])
++poz;
swap (H[poz], H[poz/2]);
}
}
void parc () {
for (int i=1, t=A[1].T; i <= N && t >= 1; --t) {
while (i <= N && A[i].T == t) {
H[++NH] = A[i++].L;
heap_u ();
}
if (NH >= 1) {
Lana += H[1];
H[1] = H[NH--];
heap_d ();
}
}
}
void afs () {
printf ("%lld", Lana);
}
int main () {
freopen ("lupu.in", "r", stdin);
freopen ("lupu.out", "w", stdout);
cit ();
sort (A+1, A+N+1, cmp);
parc ();
afs ();
return 0;
}