Pagini recente » Cod sursa (job #604620) | Cod sursa (job #422428) | Cod sursa (job #1488766) | Cod sursa (job #2261690) | Cod sursa (job #439721)
Cod sursa(job #439721)
#include <cstdio>
#include <deque>
#include <algorithm>
#include <vector>
using namespace std;
#define FIN "gutui.in"
#define FOUT "gutui.out"
bool sortPredicate(const pair<int, int> &a, const pair<int, int> &b) {
return (a.first == b.first) ? (a.second > b.second) : (a.first < b.first);
}
bool greaterEq(const int &a, const int &b) {
return a >= b;
}
void moveDequeHeap(deque<int>& Q, vector<int>& V) {
while(Q.size()) {
V.push_back(Q.back());
push_heap(V.begin(), V.end(), greaterEq);
Q.pop_back();
}
return;
}
int main() {
FILE *fin = fopen(FIN, "rt");
FILE *fout = fopen(FOUT, "wt");
int n, h, u;
fscanf(fin, "%d %d %d", &n, &h, &u);
vector< pair <int, int> > A;
int x, y;
for (int i = 0; i < n; i++) {
fscanf(fin, "%d %d", &x, &y);
if (h >= x) A.push_back(pair<int, int>(1 + (h - x) / u, y));
}
sort(A.begin(), A.end(), sortPredicate);
deque<int> Q;
vector<int> V;
int interval = (A.size()) ? (A[0].first) : 0;
for (vector< pair<int, int> >::iterator i = A.begin(); i < A.end();) {
if (i->first > interval) {
interval++;
moveDequeHeap(Q, V);
continue;
}
if (Q.size() < interval - V.size()) Q.push_back(i->second);
else if (V.size() != 0 && V.front() < i->second) {
pop_heap(V.begin(), V.end(), greaterEq);
V.pop_back();
Q.push_back(i->second);
}
i++;
}
moveDequeHeap(Q, V);
int sum = 0;
for (vector<int>::iterator i = V.begin(); i < V.end(); i++) sum += (*i);
fprintf(fout, "%d\n", sum);
fclose(fin);
fclose(fout);
return 0;
}