Pagini recente » Cod sursa (job #1600690) | Cod sursa (job #699) | Cod sursa (job #1266996) | Cod sursa (job #1392578) | Cod sursa (job #1414088)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
fstream fin("lupu.in", ios::in);
fstream fout("lupu.out", ios::out);
#define MAXN 100005
#define father(x) x / 2
#define l_son(x) x * 2
#define r_son(x) x * 2 + 1
int N, X, L, maxx;
unsigned long long int sol;
vector <long long int> sheeps[MAXN];
int heap[MAXN];
void read()
{
fin >> N >> X >> L;
for (int i = 1, w, z, gr; i <= N; i++){
fin >> w >> z;
if (w > X) continue;
if(w > 0) gr = (w - 1) / L + 1;
else gr = 0;
if (gr > maxx) maxx = gr;
sheeps[gr].push_back(z);
}
fin.close();
}
void percolate(int k)
{
while (k > 1 && heap[father(k)] < heap[k])
swap(heap[k], heap[father(k)]),
k = father(k);
}
void cut()
{
heap[1] = heap[heap[0]--];
int son, k = 1;
do{
son = l_son(k);
if (heap[r_son(k)] > heap[son]) son = r_son(k);
if (son > heap[0] || heap[son] < heap[k]) son = 0;
if (son)
swap(heap[k], heap[son]),
k = son;
} while (son);
}
int main()
{
read();
for (int i = 0; i <= maxx; i++){
while (!sheeps[i].empty()){
//heap.push(sheeps[i].back());
heap[++heap[0]] = sheeps[i].back();
percolate(heap[0]);
sheeps[i].pop_back();
}
int add = 0;
//if (heap.size()) add = heap.top(), heap.pop();
if (heap[0]) add = heap[1], cut();
sol += add;
}
fout << sol << "\n";
fout.close();
return 0;
}