Pagini recente » Cod sursa (job #2927802) | Cod sursa (job #1140761) | Cod sursa (job #1561045) | Cod sursa (job #1576033) | Cod sursa (job #1258397)
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
class Heap{
private: vector <pair <int, int>> heap;
public:
Heap(){
heap.push_back(pair<int, int>(-1, -1));
}
void insert(pair <int, int> a){
heap.push_back(a);
hyup();
}
void hyup(){
int i = heap.size()-1;
while (i != 1 && heap[i / 2].second < heap[i].second){
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].second > heap[2 * i + 1].second) {
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].second << " ";
cout << endl;
for (int i = 1; i <heap.size(); i++)
cout << heap[i].first << " ";
cout << endl;
cout << endl;
}
int maxh(){
if (heap.size() != 1) {
int x = heap[1].second;
swap (heap[1], heap.back());
heap.pop_back();
hydown(1);
return x;
}
return 0;
}
void update(int l,int x){
int c = 1;
while (c != 0){
c = 0;
for (int i = 1; i<heap.size(); i++)
if (heap[i].first + l > x){
swap(heap[i], heap.back());
heap.pop_back();
hydown(i);
c = 1;
}
}
}
bool isEmpty(){
if (heap.size() <= 1) return 1;
else return 0;
}
};
int main(){
ifstream f("lupu.in");
ofstream g("lupu.out");
int n,x,l,i=0;
Heap heap;
f >> n >> x >> l;
for (i = 0; i <n; i++){
int a, b;
f >> a >> b;
if (a <= x) heap.insert(pair<int,int> (a,b));
}
int lupu = 0;
int d = l;
while (!heap.isEmpty()){
lupu += heap.maxh();
heap.update(d, x);
d += l;
}
g << lupu;
g.close();
f.close();
cin.get();
return 0;
}