Cod sursa(job #1258527)

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