Cod sursa(job #437439)

Utilizator eXtremeCornea Tudor eXtreme Data 9 aprilie 2010 18:40:30
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.1 kb
#include<fstream>
#include<algorithm>
#include<vector>

#define NMAX 100
#define GMAX 1000

struct Gutui{ int H, G; };

/************/
int N, Hmax, Delta;
int maxNiv;
std::vector <Gutui> gutui;
int best[10000];
int uz[10000];
int GMax;
/************/

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

void read(const char * fname){
   std::ifstream in(fname);
   in>>N>>Hmax>>Delta;
   Gutui gt;
   for(int i=0; i<N; ++i){
   	in>>gt.H>>gt.G;
   	gutui.push_back(gt);
   	if( (Hmax-gt.H)/Delta + 1 > maxNiv )
		   maxNiv=(Hmax-gt.H)/Delta + 1;
	}
   
   in.close();
}   

void sol(){
	unsigned i=0;
	int nbest=0;
	
	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]=i+1; GMax+=gutui[i].G;
				++nbest;	
				break;
				}
		}
	++i;	
	}   
}    

int main(){
   read("gutui.in");
  
   std::sort(gutui.begin(), gutui.end(), cmp);
   sol();
  
 	std::ofstream out("gutui.out");
 	out<<GMax;
	out.close();  
 //system("pause");   
 return 0;  
}