Cod sursa(job #441652)

Utilizator mircovicMircea Traichioiu mircovic Data 13 aprilie 2010 01:14:03
Problema Gutui Scor 90
Compilator cpp Status done
Runda teme_upb Marime 1.92 kb
#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;
}