Cod sursa(job #438203)

Utilizator _anonymousOnose Cristi _anonymous Data 10 aprilie 2010 16:06:36
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 1.66 kb
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <fstream>
#include <sstream>
#include <string>
#include <map>


using namespace std;  




int main(){

multimap<int, int, std::greater<int> > gutui;
ifstream in( "gutui.in" );
ofstream out( "gutui.out" );
string line;
typedef pair <int, int> Int_Pair;
   

int v[3];
int i=0, j=0, x, k=0, y;
int N, H, U;

getline (in, line);
string numar;
for(i=0; i<=line.size(); i++){						   
       if(line[i] != ' ' )  numar.push_back( line[i] );		   						
else{
	 istringstream r( numar );
	 r>>x;
	 v[j] = x;
	 numar.clear();
	 j++;
	 }
}
istringstream r( numar );
r>>x;
v[j] = x;
numar.clear();

N = v[0]; H = v[1]; U = v[2];

int inaltime[N];
int greutate[N];

while (! in.eof() ){
	  getline (in, line);
	  for(i=0; i<=line.size(); i++){					   
	  if(line[i] != ' ' ) numar.push_back( line[i] );		   						 
	  			 else {
				 	   istringstream r( numar );
					   r>>y;
					   numar.clear();	  
					  }
           
       }   
	   istringstream r( numar );
	   r>>x;
	   gutui.insert ( Int_Pair ( y, x ) );
	   numar.clear();  
	   k++; 
}


multimap<int, int>::iterator it;

multimap<int, int > rez;

for(it = gutui.begin();it != gutui.end();it++){
	   if(H >= it->first ){
	   		rez.insert( Int_Pair ( it->second, it->first ) );
  			H=H-U;
			}
			else{
				 if(!rez.empty())
				 if( it->second > (rez.begin())->first ){
				 	 rez.erase(rez.begin());
				 	 rez.insert( Int_Pair ( it->second, it->first ) );
				 }
		 		 }
}

int max=0;
for(it = rez.begin();it != rez.end();it++){
	   max += it->first;
}
out<<max;
return 0;

}