Pagini recente » Istoria paginii runda/teza11b/clasament | Profil 8carolinee3785yM0 | Istoria paginii utilizator/krineraq1v | Autentificare | Cod sursa (job #441652)
Cod sursa(job #441652)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 100000
using namespace std;
typedef struct {
int h, g, pos;
} gutuie;
vector<gutuie> myVector;
bool comparaPos(const gutuie& a, const gutuie& b){
return a.pos < b.pos;
}
bool comparaGr(const gutuie a, const gutuie b){
return a.g < b.g;
}
int main(int argc, char* argv[]){
ifstream fin;
ofstream fout;
fin.open("gutui.in");
fout.open("gutui.out");
int n, h, u;
fin>>n>>h>>u;
for(int i = 0; i < n; i++){
gutuie aux;
fin>>aux.h>>aux.g;
aux.pos = (h - aux.h) / u;
myVector.push_back(aux);
}
//for (int i=0; i<myVector.size(); i++) cout << " " << myVector[i].pos<< " "<< myVector[i].h << " " << myVector[i].g<<endl;
sort(myVector.begin(), myVector.end(), comparaPos);
vector<gutuie> myHeap;
int greutate = 0, currentPos = 0, oldPos = myVector.back().pos + 1;
while(myVector.size() > 0 && myVector.back().pos >= 0){
currentPos = myVector.back().pos;
//cout<<"CurrentPos: "<<currentPos<<" "<<"Gr "<<myVector.back().g<<endl;
while(myVector.size() > 0 && myVector.back().pos == currentPos){
myHeap.push_back(myVector.back());
myVector.pop_back();
push_heap(myHeap.begin(), myHeap.end(), comparaGr);
}
//make_heap(myHeap.begin(), myHeap.end(), comparaGr);
for(int j = 0; j < oldPos - currentPos; j++){
pop_heap(myHeap.begin(), myHeap.end(), comparaGr);
greutate += myHeap.back().g;
//cout<<"Greutate "<<greutate<<" Curenta:"<< myHeap.back().g<<endl;
myHeap.pop_back();
}
oldPos = currentPos;
}
while(currentPos > 0){
pop_heap(myHeap.begin(), myHeap.end(), comparaGr);
greutate += myHeap.back().g;
//cout<<"Greutate "<<greutate<<" Curenta:"<< myHeap.back().g<<endl;
myHeap.pop_back();
currentPos--;
}
fout<<greutate<<endl;
fin.close();
fout.close();
return 0;
}