Cod sursa(job #438245)

Utilizator _anonymousOnose Cristi _anonymous Data 10 aprilie 2010 16:37:28
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 1.56 kb
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <fstream>
#include <sstream>
#include <string>
#include <map>
using namespace std;

int main(){
multimap<long, long, std::greater<long> > gutui;
ifstream in( "gutui.in" );
ofstream out( "gutui.out" );
string line;
typedef pair <long, long> Int_Pair;
long v[3];
long i=0, j=0, x, k=0, y;
long 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];
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<long, long>::iterator it;
multimap<long, long > 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 ) );
				 }
		 		 }
}
long max=0;
for(it = rez.begin();it != rez.end();it++){
	   max += it->first;
}
out<<max;
in.close(); out.close();
return 0;
}