Cod sursa(job #1318984)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 16 ianuarie 2015 15:54:08
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.58 kb
/*
	Fiecarei oi ii asociem un timp. Un timp de t inseamna ca oaia poate fi
	alesa doar inainte de t alegeri ale lupului.
	Sortam oile dupa timp.
	Fie best[i] = oaia care da cea mai multa lana si poate fi aleasa
	cel tarziu la timpul i si nu a fost aleasa anterior.
	Solutia este best[t_max] + best[t_max - 1] + ... best[0]
	Ca sa gasim best[i] folosim o coada de prioritati in care avem doar oile
	cu t >= i
*/
#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;
}