Pagini recente » Cod sursa (job #1568572) | Cod sursa (job #1772309) | Cod sursa (job #1637952) | Cod sursa (job #2067225) | Cod sursa (job #436425)
Cod sursa(job #436425)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
struct gutuie {
unsigned int height;
unsigned int weight;
};
class compare {
int hmax, nivel;
public:
compare(int i, int j) : hmax(i), nivel(j) {};
bool operator()(gutuie x, gutuie y) {
return (((hmax - x.height) / nivel) + 1 < ((hmax - y.height) / nivel) + 1)
|| (!(((hmax - y.height) / nivel) + 1 < ((hmax - x.height) / nivel) + 1) && (x.weight > y.weight));
}
};
class minHeapCompare {
public:
bool operator () (int a, int b) {
return a > b;
}
};
int main() {
unsigned int n, h, u, dim;
gutuie g;
vector<gutuie> gutui;
vector<int> nivel;
//vector<unsigned int> best;
priority_queue< int, vector<int>, greater<int> > best;
ifstream fin("gutui.in");
fin >> n >> h >> u;
for (int i = 0; i < n; i++) {
fin >> g.height >> g.weight;
gutui.push_back(g);
}
fin.close();
sort(gutui.begin(), gutui.end(), compare(h, u));
for (int i = 0; i < n; i++)
nivel.push_back(((h - gutui[i].height) / u) + 1);
nivel.push_back(nivel[n - 1] + 1);
int i = 0, niv = nivel[0];
int ad = 0;
while (i < n) {
if (nivel[i] == niv && ad < niv) {
//best.push_back(gutui[i].weight);
//push_heap(best.begin(), best.end(), minHeapCompare());
best.push(gutui[i].weight);
ad++;
if (nivel[i + 1] > niv) {
while (best.size() > niv) {
//pop_heap(best.begin(), best.end(), minHeapCompare());
//best.pop_back();
best.pop();
}
niv = nivel[i + 1];
ad = 0;
}
i++;
}
else if (nivel[i] == niv && ad == niv) {
if (nivel[i + 1] > niv) {
while (best.size() > niv) {
//pop_heap(best.begin(), best.end(), minHeapCompare());
//best.pop_back();
best.pop();
}
niv = nivel[i + 1];
ad = 0;
}
i++;
}
}
unsigned int gmax = 0;
while (best.size() > 0) {
gmax += best.top();
best.pop();
}
ofstream fout("gutui.out");
fout << gmax << endl;
fout.close();
return 0;
}