Cod sursa(job #1318982)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 16 ianuarie 2015 15:47:02
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

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

const int  Nmax = 100005;
typedef long long int int64;

int n, x, l;
int has_time[Nmax];
int reward[Nmax];
int ind[Nmax];

struct compare1 {
	bool operator () (int i, int j) { return reward[i] < reward[j]; }
};

priority_queue<int, vector<int>, compare1> prt_queue;

struct compare2 {
	bool operator () (int i, int j) { return has_time[i] < has_time[j]; }
} comp;


int main() {
	int distance;
	int max_has_time = 0;
	int64 result = 0;

	in >> n >> x >> l;
	for (int i = 1; i <= n; ++i) {
		in >> distance >> reward[i];
		if (distance > x) has_time[i] = -1;
		else has_time[i] = (x - distance) / l;

		max_has_time = max(max_has_time, has_time[i]);
		ind[i] = i;
	}
	sort(ind + 1, ind + n + 1, comp);

	for (int i = n, j = max_has_time; j >= 0; --j) {
		while (has_time[ind[i]] >= j && i > 0) {
			prt_queue.push(ind[i]);
			--i;
		}
		if (!prt_queue.empty()) {
			result += reward[prt_queue.top()];
			prt_queue.pop();
		}
	}

	out << result << '\n';

	return 0;
}