Cod sursa(job #437355)

Utilizator Andrei.RaduAndrei Radu Andrei.Radu Data 9 aprilie 2010 17:11:23
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 1.82 kb
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <limits>
using namespace std;
const string in = "gutui.in";
const string out = "gutui.out";
class gutuie{
  public:
    //inaltime si valoare
    unsigned int h,v;
    bool operator< (const gutuie& p_gut) const{
	//if(h == p_gut.h){return v < p_gut.v;}
	return (v < p_gut.v);
    }
    bool operator<= (const gutuie& p_gut) const{
	//if(h == p_gut.h){return v < p_gut.v;}
	return (v < p_gut.v);
    }
};
inline unsigned int clamp(unsigned int i, unsigned int n){return i<n?i:n;}
bool lessh(const gutuie& g1, const gutuie&g2){return g1.h < g2.h;}
bool lessv(const gutuie& g1, const gutuie&g2){return g1.v > g2.v;}
int main(){
  ifstream str_in;
  ofstream str_out;
  str_in.open(in.c_str(), ifstream::in);
  str_out.open(out.c_str(), ifstream::out);
  unsigned int n,h,d;
  str_in>>n>>h>>d;
  vector<gutuie> gut_vect(n);
  for(unsigned int i = 0; i < n;++i){
    str_in>>gut_vect[i].h>>gut_vect[i].v;
    if(gut_vect[i].h > h){i--;n--;};
  }
  gut_vect.resize(n);
  
  sort(gut_vect.begin(),gut_vect.end(),lessh);
  
  for(unsigned int i = 0; i < n;++i){
      //cout<<gut_vect[i].h<<" "<<gut_vect[i].v<<endl;
  }
  priority_queue< gutuie > pr;
  //if((gut_vect[n-1].h)%d == 0){h++;}
  unsigned int w = 0;
  for(unsigned int i = ((gut_vect[0].h)/d) * d,j = 0; i <= h;){
      //cout<<j<<" "<<i<<" "<<i+d<<endl;//" "<<gut_vect[j].h<<endl;
      if(gut_vect[j].h <= i && j < n){
	  //cout<<"*Inserting "<<gut_vect[j].h<<" "<<gut_vect[j].v<<endl;
	  pr.push(gut_vect[j]);
	  j++;
	  continue;
      }
      if(!pr.empty()){
	//cout<<"*Extracting "<<pr.top().h<<" "<<pr.top().v<<endl;
	w += pr.top().v;
	pr.pop();
      }
      //else{break;};
      
      i += d ;
  }
  str_out<<w<<endl;
  //<<rez[n-1].first<<endl;
  return 0;
}