Cod sursa(job #3243707)

Utilizator RosheRadutu Robert Roshe Data 20 septembrie 2024 15:07:16
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 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;

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

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(D, F);	
	}
	sort(H, H+N);
	//for(int i = 0; i<N; i++)
	//	cout << H[i].first << " " << H[i].second << endl;
	int T = H[N-1].first;
	int it = N-1;
	long long total = 0;
	while(T-- >= 0){
		while(it >= 0 && H[it].first >= T){
			pq.push(H[it]);
			it--;
		}
		if(pq.empty() == false){
			total+=pq.top().second;
			pq.pop();	
		}
	}
cout << total;
}