Cod sursa(job #1258397)

Utilizator cioionutFMI Ionut Ciocoiu cioionut Data 8 noiembrie 2014 20:26:07
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 2 kb
#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;
}