Cod sursa(job #438804)

Utilizator eXtremeCornea Tudor eXtreme Data 11 aprilie 2010 00:44:52
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.99 kb
#include<algorithm>
#include<fstream>
#include<vector>
#define NIV(k) ( (Hmax-(k))/Delta + 1)
struct Gutui{ int H, G; };

int N, Hmax, GMax, Delta, maxNiv;
std::vector <Gutui> gutui;
std::vector<bool> best; 

bool cmp(const Gutui &x, const Gutui &y){
    return x.G > y.G;
}

void read(const char * fname){
  
}   

void sol(){
	unsigned i=0;
	int nbest=0;
	for(int k=0; k<maxNiv; ++k) best.push_back(false);
	while( nbest<maxNiv && i<gutui.size() ){
		for(int j=maxNiv-1; j>=0; --j){
		  if( (gutui[i].H+j*Delta) <= Hmax )
		  	 if( !best[j] ){
				best[j]=1; GMax+=gutui[i].G;
				++nbest;	
				break;
				}
		}
	++i;	
	}   
}    

int main(){
 std::ifstream in("gutui.in");
 std::ofstream out("gutui.out");
 in>>N>>Hmax>>Delta;
 Gutui tmp;
 for(int i=0;i<N;++i){
  in>>tmp.H>>tmp.G;
  gutui.push_back(tmp);
  if(NIV(tmp.H) > maxNiv) maxNiv=NIV(tmp.H);
 }
	
  std::sort(gutui.begin(), gutui.end(), cmp);
  sol();
  out<<GMax;
  out.close();  
 return 0;  
}