Pagini recente » Cod sursa (job #2266211) | Cod sursa (job #146199) | Cod sursa (job #198507) | Cod sursa (job #1300123) | Cod sursa (job #436871)
Cod sursa(job #436871)
#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;
}