Pagini recente » Cod sursa (job #2366701) | Cod sursa (job #1384177) | Cod sursa (job #2567077) | Cod sursa (job #1252349) | Cod sursa (job #435702)
Cod sursa(job #435702)
#include <cstdio>
#include <cstdlib>
#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) {
if (a.first == b.first) return a.second > b.second;
else return 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>((h - x) / u, y));
}
sort(A.begin(), A.end(), sortPredicate);
for (int i = 0; i < A.size(); i++) printf("%d %d\n", A[i].first, A[i].second);
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());
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;
}