Pagini recente » Cod sursa (job #1395552) | Cod sursa (job #1816043) | Cod sursa (job #3210207) | Cod sursa (job #1074497) | Cod sursa (job #436893)
Cod sursa(job #436893)
#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{
//if(h == p_gut.h){return v < p_gut.v;}
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){
if(gut_vect[i].h <= h){
rez[i].first = gut_vect[i].v;
rez[i].second = 1;
}
else{rez[i].first = rez[i].second = 0;}
//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){
int nr = ((rez[j].second * d + gut_vect[i].h) <= h)?(gut_vect[i].v):0;
//cout<<rez[j].second * d + gut_vect[i].h<<" "<<h<<"NR"<<nr<<endl;
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<<"B "<<rez[j].second<<" "<<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;
}