Pagini recente » Cod sursa (job #2890695) | Cod sursa (job #463569) | Cod sursa (job #2945708) | Cod sursa (job #2829087) | Cod sursa (job #463390)
Cod sursa(job #463390)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
//structura pentru gutuie
typedef struct a {
int h;
int w;
} gutuie;
//functie de comparatie necesara sortarii
bool isGreater (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; //valoare aux pentru citire
input >>N >>H >>U;
vector<gutuie> gutui; //valorile gutuilor
vector<gutuie>::iterator it; //iterator pe gutui
vector<int> heap; //heapul ce tine valorile gutuilor
make_heap (heap.begin(),heap.end()); //initializare heap
for (i=0;i<N;i++) { //citire
input >>read.h >>read.w;
read.h = (int)((H-read.h)/U) + 1;
gutui.push_back(read); //nivel
}
input.close();
sort(gutui.begin(), gutui.end(), isGreater); //sortez descrescator dupa nivel
nivel = gutui[0].h;
int s=0;
for (it = gutui.begin(); it!=gutui.end(); ++it) { // pentru fiecare gutuie
while (nivel > it->h) { // daca nivelul_curent > nivelul gutuii
if (heap.size()) {
pop_heap(heap.begin(),heap.end()); // inseamna ca pot lua gutui de pe nivelurile anterioare
s += heap.back();
heap.pop_back();
}
nivel--;
}
heap.push_back(it->w); push_heap(heap.begin(), heap.end()); // pun (fiecare) gutuie in heap
}
while (nivel && heap.size()){ // daca mai pot lua gutui (si mai am de unde)
pop_heap(heap.begin(), heap.end());
s += heap.back(); // extrag gutuile ramase
heap.pop_back();
nivel--;
}
output.open ("gutui.out", ios::out);
output << s;
output.close();
return 0;
}