Pagini recente » Cod sursa (job #1770501) | Cod sursa (job #453309) | Cod sursa (job #228176) | Cod sursa (job #1699621) | Cod sursa (job #438860)
Cod sursa(job #438860)
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
struct Gutui {
int h, w;
friend bool operator<(Gutui const& a, Gutui const& b) {
return a.h < b.h; // or (a.h == b.h and a.w < b.w);
}
friend bool operator>(Gutui const& a, Gutui const& b) {
return b < a;
}
friend std::ostream& operator<<(std::ostream& s, Gutui const& v) {
s << '(' << v.h << ", " << v.w << ')';
return s;
}
};
/*
template<class T, class C, T C::*M>
struct sum {
T operator()(T const& cur, C const& next) { return cur + next.*M; }
};
*/
int solve(std::vector<Gutui> gutui, int H, int U) {
std::sort(gutui.begin(), gutui.end(), std::greater<Gutui>()); //>
int picked_weight = 0;
std::vector<int> available_weights;
int top;
int offset = H % U;
if (offset == U) top = 0;
else top = offset - U;
while ((gutui.size() or available_weights.size()) and top <= H) {
if (available_weights.size()) {
picked_weight += available_weights.front();
std::pop_heap(available_weights.begin(), available_weights.end());
available_weights.pop_back();
top += U;
}
else {
top += U * std::max(1, (gutui.back().h - top) / U);
}
while (gutui.size() and gutui.back().h <= top) {
available_weights.push_back(gutui.back().w);
std::push_heap(available_weights.begin(), available_weights.end());
gutui.pop_back();
}
}
return picked_weight;
}
int main() {
FILE* fd1;
FILE* fd2;
fd1=fopen("gutui.out", "w");
fd2=fopen("gutui.in", "r");
int numargutui, height, step;
fscanf(fd2, "%i %i %i", &numargutui, &height, &step);
Gutui data[numargutui];
int i;
for (i = 0; i < numargutui; i++)
fscanf(fd2, "%i %i ", &(data[i].h), &(data[i].w));
std::vector<Gutui> v (data, data + numargutui); // nombergutui sau +-1?
int actual = solve(v, height, step);
fprintf(fd1, "%i ", actual);
fclose(fd2);
fclose(fd1);
}