Cod sursa(job #436765)

Utilizator Andrei.RaduAndrei Radu Andrei.Radu Data 8 aprilie 2010 22:44:56
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.47 kb
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
const string in = "gutui.in";
const string out = "gutui.out";
class gutuie{
  public:
    //inaltime si valoare
    int h,v;
    bool operator<(const gutuie& p_gut) const{
	return (h > p_gut.h);
    }
};
int main(){
  ifstream str_in;
  ofstream str_out;
  str_in.open(in.c_str(), ifstream::in);
  str_out.open(out.c_str(), ifstream::out);
  int n,h,d;
  str_in>>n>>h>>d;
  vector<gutuie> gut_vect(n);
  vector< pair<int,int> > rez(n);
  
  for(int i = 0; i < n;++i){
    str_in>>gut_vect[i].h>>gut_vect[i].v;
  }
  
  sort(gut_vect.begin(),gut_vect.end());
  
  
  for(int i = 0; i < n;++i){
      rez[i].first = gut_vect[i].v;
      rez[i].second = 1;
    
      //cout<<gut_vect[i].h<<" "<<gut_vect[i].v<<endl;
  }
  
  for(int i = 0; i < n; ++i){
    //cout<<"**I "<<i<<endl;
    for(int j = 0; j < i; ++j){
      //cout<<rez[j].second * d + gut_vect[i].h<<" "<<h<<endl;
      int nr = ((rez[j].second * d + gut_vect[i].h) <= h)?(gut_vect[i].v):0;
      int temp= rez[j].first + nr;
      if(temp > rez[i].first){
	  //cout<<"**J "<<j<<" "<<gut_vect[j].v<<" "<<rez[j].second * d<<" "<< (nr>0) <<endl;
	  rez[i].first = temp;
	  rez[i].second = rez[j].second + (nr>0) ? 1 : 0;
	  //cout<<rez[i].second<<" "<<rez[i].first<<endl;
      }
    }
    //cout<<"GUT FIN "<<i<<" "<<rez[i].first<<" "<<rez[i].second<<endl;
  }
  str_out<<rez[n-1].first<<endl;
  return 0;
}