Pagini recente » Istoria paginii utilizator/david_popa123 | Profil St3faN | hektor | Cod sursa (job #2014112) | Cod sursa (job #440486)
Cod sursa(job #440486)
#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(argv[1]);
fout.open(argv[2]);
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;
make_heap (myHeap.begin(),myHeap.end(), comparaGr);
int greutate = 0;
while(myVector.size() > 0){
int currentPos = myVector.back().pos;
while(myVector.size() > 0 && myVector.back().pos == currentPos){
myHeap.push_back(myVector.back());
myVector.pop_back();
push_heap(myHeap.begin(), myHeap.end(), comparaGr);
}
pop_heap(myHeap.begin(), myHeap.end(), comparaGr);
greutate += myHeap.back().g;
myHeap.pop_back();
}
fout<<greutate<<endl;
fin.close();
fout.close();
return 0;
}