Cod sursa(job #3243715)

Utilizator RosheRadutu Robert Roshe Data 20 septembrie 2024 15:29:52
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <utility>
#include <algorithm>

using namespace std;

const int N = 1e5+1;

ifstream in("lupu.in");
ofstream out("lupu.out");

pair< int, int> H[N];
priority_queue<pair<int,int>, vector<pair<int,int> > > pq;

struct fcmp{
bool operator()(const pair<int,  int>& a, const pair<int, int>& b){
  if (a.second < b.second) return true;
  if (a.second > b.second) return false;
  if (a.first < b.first) return true;
  return false;
}
}fcmp;


int main(){
  int N, X, L;
  in >> N >> X >> L;
	for(int i = 0; i<N; i++){
		int D, F;
		in >> D >> F; 
		D = (X - D) / L;
		H[i] = make_pair(F, D);	
	}
	sort(H, H+N, fcmp);
	//for(int i = 0; i<N; i++)
	//	cout << H[i].first << " " << H[i].second << endl;
	int T = H[N-1].second;
	int it = N-1;
	long long total = 0;
	while(T >= 0){
		while(it >= 0 && H[it].second >= T){
			pq.push(H[it]);
			it--;
		}
		if(pq.empty() == false){
			total+=pq.top().first;
			pq.pop();	
		}
		T--;
	}
out << total;
}