Pagini recente » Cod sursa (job #443414) | Cod sursa (job #2021007) | Cod sursa (job #1222814) | Cod sursa (job #1606795) | Cod sursa (job #95529)
Cod sursa(job #95529)
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N_MAX = 100010;
const int INF = 2000000000;
int size = 0;
pair <int, int> H[N_MAX], vec[N_MAX];
void push(int t, int l)
{
pair <int, int> kkt, aux;
kkt = make_pair(t, l);
H[++ size] = kkt;
int poz = size;
while ((poz >> 1) >= 1 && H[poz].second > H[poz >> 1].second) {
aux = H[poz >> 1];
H[poz >> 1] = H[poz];
H[poz] = aux;
poz >>= 1;
}
}
void pop(int poz)
{
H[poz] = H[size];
H[size] = make_pair(0, 0);
size --;
int sch;
pair <int, int> aux;
while (((poz << 1) <= size || ((poz << 1) + 1) <= size) && (H[poz].second < H[poz << 1].second || H[poz].second < H[(poz << 1) + 1].second)) {
if (H[poz << 1].second > H[(poz << 1) + 1].second) sch = poz << 1;
else sch = (poz << 1) + 1;
// if (kkt == 1) printf("%d\n", sch);
aux = H[poz];
H[poz] = H[sch];
H[sch] = aux;
poz = sch;
}
// if (kkt == 1) printf("\n");
}
int cmp(pair <int, int> a, pair <int, int> b)
{
return (a.first > b.first);
}
int main()
{
freopen("lupu.in", "r", stdin);
#ifndef _SCREEN_
freopen("lupu.out", "w", stdout);
#endif
int N, X, L, i, y, l;
scanf("%d %d %d\n", &N, &X, &L);
for (i = 1; i <= N; i ++) {
scanf("%d %d\n", &y, &l);
vec[i] = make_pair((X - y) / L, l);
}
sort(vec + 1, vec + N + 1, cmp);
int tmax = vec[1].first, poz = 1, rez = 0, j;
for (i = tmax; i >= 0; i --) {
while (vec[poz].first == i && poz <= N) {
push(i, vec[poz].second);
poz ++;
}
rez += H[1].second;
pop(1);
}
printf("%d\n", rez);
return 0;
}