Pagini recente » Cod sursa (job #1279917) | Cod sursa (job #1041540) | Cod sursa (job #2453141) | Cod sursa (job #2575944) | Cod sursa (job #1318984)
/*
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;
}