Cod sursa(job #3143120)

Utilizator daristyleBejan Darius-Ramon daristyle Data 27 iulie 2023 18:53:06
Problema Lupul Urias si Rau Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");

const int SHEEP_MAX = 1e5;

template<typename T>
class Heap{
private:
		T heap[SHEEP_MAX];
		int heapSize;

		inline int parent(int i){
			return (i - 1) / 2;
		}

		inline int leftChild(int i){
			return 2 * i + 1;
		}

		inline int rightChild(int i){
			return 2 * i + 2;
		}

		void upHeap(int i){
			while(i && heap[i] < heap[parent(i)]){
				swap(heap[i], heap[parent(i)]);
				i = parent(i);
			}
		}

		void downHeap(int i){
			int smallest = i, left = leftChild(i), right = rightChild(i);

			if(left < heapSize && heap[left] < heap[smallest])
				smallest = left;
			if(right < heapSize && heap[right] < heap[smallest])
				smallest = right;

			if(smallest != i){
				swap(heap[i], heap[smallest]);
				downHeap(smallest);
			}
		}

public:
		Heap(){
			heapSize = 0;
		}

		void insert(T x){
			heap[heapSize++] = x;
			upHeap(heapSize - 1);
		}

		T query(){
			return heap[0];
		}

		void extractRoot(){
			swap(heap[0], heap[heapSize - 1]);
			--heapSize;
			downHeap(0);
		}

		void clear(){
			heapSize = 0;
		}
};

struct Sheep{
		unsigned int wool, distance;

		friend ifstream& operator>>(ifstream& fin, Sheep& s){
			fin >> s.distance >> s.wool;
			return fin;
		}

		friend ofstream& operator<<(ofstream& fout, const Sheep& s){
			fout << s.distance << ' ' << s.wool << '\n';
			return fout;
		}
};

struct unsignedint{
		unsigned int x;

		bool operator<(const unsignedint& other) const{
			return x > other.x;
		}
};

Sheep v[SHEEP_MAX + 1];
Heap<unsignedint> maxHeap;

bool cmp(const Sheep& a, const Sheep& b){
	if(a.distance == b.distance)
		return a.wool > b.wool;
	return a.distance > b.distance;
}

int main(){
	unsigned int sheep, x, l, n = 0;
	fin >> sheep >> x >> l;

	for(int i = 0; i < sheep; ++i){
		Sheep aux;
		fin >> aux;

		if(aux.distance <= x){
			aux.distance = (x - aux.distance) / l + 1;
			v[n++] = aux;
		}
	}

	sort(v, v + n, cmp);

	int j = 0;
	long long sum = 0;
	v[n].distance = 0;
	for(int i = v[0].distance; i > 0; --i){
		while(j < n && v[j].distance == i){
			maxHeap.insert({v[j].wool});
			++j;
		}

		sum += maxHeap.query().x;
		maxHeap.extractRoot();
	}

	fout << sum << '\n';

	fin.close();
	fout.close();
	return 0;
}