Pagini recente » Cod sursa (job #1450488) | Cod sursa (job #2246093) | Cod sursa (job #2777273) | Cod sursa (job #1268676) | Cod sursa (job #1258527)
#include<iostream>
#include<fstream>
#include<vector>
#include<map>
using namespace std;
class Heap{
private: vector <int> heap;
public:
Heap(){
heap.push_back(-1);
}
void insert(int a){
heap.push_back(a);
hyup();
}
void hyup(){
int i = heap.size()-1;
while (i != 1 && heap[i / 2]< heap[i]){
swap(heap[i / 2], heap[i]);
i /= 2;
}
}
void hydown(int i){
int n = heap.size();
while (i<n){
if (i * 2<n && i * 2 + 1<n) {
if (heap[2 * i]> heap[2 * i + 1]) {
swap(heap[2 * i], heap[i]);
i *= 2;
}
else {
swap(heap[2 * i+1], heap[i]);
i *= 2+1;
}
}
else {
if (i * 2<n) {
swap(heap[2 * i], heap[i]);
i *= 2;
}
else if (i * 2 + 1<n) {
swap(heap[2 * i + 1], heap[i]);
i *= 2 + 1;
}
else i *= 2;
}
}
}
void print(){
for (int i = 1; i <heap.size() ; i++)
cout << heap[i]<< " ";
cout << endl;
}
int maxh(){
if (heap.size() != 1) {
int x = heap[1];
swap (heap[1], heap.back());
heap.pop_back();
hydown(1);
return x;
}
return 0;
}
bool isEmpty(){
if (heap.size() <= 1) return 1;
else return 0;
}
};
int main(){
ifstream f("lupu.in");
ofstream g("lupu.out");
vector <int> t[100001];
vector <int> oi;
int n,x,l,i=0;
Heap heap;
f >> n >> x >> l;
int max = 0;
for (i = 0; i <n; i++){
int a, b;
f >> a >> b;
int timp = (x - a) / l;
t[timp].push_back(i);
oi.push_back(b);
if (timp>max) max = timp;
}
int lupu = 0;
for (i = max; i >= 0; i--){
for (int j = 0; j < t[i].size(); j++)
heap.insert(oi[t[i][j]]);
lupu += heap.maxh();
}
g << lupu;
g.close();
f.close();
//cin.get();
return 0;
}