Pagini recente » Cod sursa (job #475798) | Cod sursa (job #306290) | Cod sursa (job #2768236) | Cod sursa (job #2257372) | Cod sursa (job #477437)
Cod sursa(job #477437)
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
pair <int, int> a[100010];
long long s;
int h[100010], m;
void shift(int k){
int son, aux;
do {
son = 0;
if (k*2 <= m){
son = k*2;
if (k*2+1 <= m && h[k*2+1] > h[son])
son = k*2+1;
if (h[k] >= h[son])
son = 0;
}
if (son){
aux = h[k];
h[k] = h[son];
h[son] = aux;
k = son;
}
} while (son);
}
void percolate(int k){
int x = h[k];
while (k > 1 && h[k/2] < x){
h[k] = h[k/2];
k = k/2;
}
h[k] = x;
}
void insert(int x){
m++;
h[m] = x;
percolate(m);
}
int max(){
if (m == 0)
return 0;
else {
int x = h[1];
h[1] = h[m];
m--;
shift(1);
return x;
}
}
int main(){
ifstream f("lupu.in");
ofstream g("lupu.out");
int n, x, l, i, p, q;
f>>n>>x>>l;
for (i = 1; i <= n; i++){
f>>p>>q;
a[i] = make_pair(p, q);
}
sort(a+1, a+n+1);
int ap = (x - a[1].first)/l;
int dist, j = 1;
for (i = ap; i >= 0; i--){
dist = x - i*l;
while (j <= n && a[j].first <= dist){
insert(a[j].second);
j++;
}
s = s + max();
}
g<<s<<'\n';
return 0;
}