Cod sursa(job #440302)

Utilizator Andrei.RaduAndrei Radu Andrei.Radu Data 11 aprilie 2010 23:38:53
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.8 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{
	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);
  unsigned int n,h,d;
  //citeste datele din fisier
  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;
    //daca inaltimea la care se afla o gutuie este mai mare decat
    //inaltimea maxima, ignor-o
    if(gut_vect[i].h > h){i--;n--;};
  }
  str_in.close();
  //ia in calcul gutuile ignorate
  gut_vect.resize(n);
  //sorteaza vectorul de gutui dupa inaltime
  sort(gut_vect.begin(),gut_vect.end(),lessh);
  priority_queue< gutuie > pr;
  unsigned int w = 0;
  //rezolva problema pentru inaltimi maxime alese astfel incat sa se 
  //poate culege 1,2..etc gutui
  for(unsigned int i = (gut_vect[0].h) + ( h - gut_vect[0].h ) % d ,j = 0; i <= h;){
      //introdu intr-un heap toate gutuile cu inaltimea mai mica decat i
      if( j < n && gut_vect[j].h <= i ){
	  pr.push(gut_vect[j]);
	  ++j;
	  continue;
      }
      //pentru intervalul [i-d,i], alege gutuia de valoare maxima
      if(!pr.empty()){
	
	w += pr.top().v;
	pr.pop();
      }      
      //creste copacul cu d
      i+=d;
  }
  str_out.open(out.c_str(), ifstream::out);
  str_out<<w<<endl;
  return 0;
}