Pagini recente » Cod sursa (job #1810087) | Cod sursa (job #2582289) | Cod sursa (job #2458253) | Cod sursa (job #1517857) | Cod sursa (job #441787)
Cod sursa(job #441787)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
typedef struct a {
int h;
int w;
} gutuie;
bool isSmaller (gutuie a, gutuie b) {
return a.h > b.h;
}
int main () {
ifstream input;
ofstream output;
input.open ("gutui.in", ios::in);
int N,H,U,i,nivel;
gutuie read;
input >>N >>H >>U;
vector<gutuie> gutui;
vector<gutuie>::iterator it;
vector<int> heap;
make_heap (heap.begin(),heap.end());
for (i=0;i<N;i++) {
input >>read.h >>read.w;
read.h = (int)((H-read.h)/U) + 1;
gutui.push_back(read);
}
input.close();
sort(gutui.begin(), gutui.end(), isSmaller);
nivel = gutui[0].h;
int s=0;
for (it = gutui.begin(); it!=gutui.end(); ++it) {
while (nivel > it->h) {
if (heap.size()) {
pop_heap(heap.begin(),heap.end());
s += heap.back();
heap.pop_back();
}
nivel--;
}
heap.push_back(it->w); push_heap(heap.begin(), heap.end());
//cout <<it->h <<" " <<it->w <<endl;
}
while (nivel && heap.size()){
pop_heap(heap.begin(), heap.end());
s += heap.back();
heap.pop_back();
nivel--;
}
output.open ("gutui.out", ios::out);
output << s;
output.close();
return 0;
}