Pagini recente » Cod sursa (job #1864229) | Cod sursa (job #496050) | Cod sursa (job #1861228) | Cod sursa (job #2709767) | Cod sursa (job #438835)
Cod sursa(job #438835)
#include<algorithm>
#include<fstream>
#include<vector>
#include<bitset>
#define NIV(k) ( (Hmax-(k))/Delta + 1)
struct Gutui{ unsigned H, G; };
unsigned N, Hmax, GMax, Delta, maxNiv;
std::vector <Gutui> gutui;
std::bitset<100000> niv; //1 if level occupied
//std::sort compare function
bool cmp(const Gutui &x, const Gutui &y){
return x.G > y.G;
}
void solve(){
std::sort(gutui.begin(), gutui.end(), cmp);
for(unsigned i=0, nOcc=0; nOcc<maxNiv && i<N; ++i)
for(int j=maxNiv-1; j>=0; --j){
if( (gutui[i].H+j*Delta) <= Hmax && !niv[j]){
niv.set(j);
GMax+=gutui[i].G;
++nOcc;
break;
}
}
}
void read(){
std::ifstream in("gutui.in");
in>>N>>Hmax>>Delta;
Gutui tmp;
for(unsigned i=0;i<N;++i){
in>>tmp.H>>tmp.G;
gutui.push_back(tmp);
if(NIV(tmp.H) > maxNiv) maxNiv=NIV(tmp.H);
}
}
int main(){
std::ofstream out("gutui.out");
read();
solve();
out<<GMax;
out.close();
return 0;
}