Cod sursa(job #438771)

Utilizator eXtremeCornea Tudor eXtreme Data 11 aprilie 2010 00:16:10
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.96 kb
#include<algorithm>
#include<fstream>
#include<vector>
struct Gutui{ int H, G; };

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

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;
	}
}   

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]=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();  
 return 0;  
}