Cod sursa(job #441095)

Utilizator mihai.popescuPopescu Mihai mihai.popescu Data 12 aprilie 2010 19:17:46
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.4 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <functional>
#include <cstdlib>

using namespace std;

class Gutuie{
	public:
		int greutate;
		int inaltime;

};

bool compare(const Gutuie& g1,const Gutuie& g2){
if(g1.inaltime != g2.inaltime)	
	return g1.inaltime > g2.inaltime;	
else
	return g1.greutate > g2.greutate;	
}

int main(){
	
 ifstream fin("gutui.in");
 ofstream fout("gutui.out");		
	
 int n,h,u;
 
 fin>>n;
 fin>>h;
 fin>>u;	
	
 vector<Gutuie> v;
 vector<int> kg;
 
 int i,caz,contor;
 
 for(i = 0; i < n; i++){
	 Gutuie g;
	 fin>>g.inaltime;
	 fin>>g.greutate;
	 v.push_back(g); 
	} 	

 std::sort(v.begin(),v.end(),compare);
 //make_heap(kg.begin(),kg.end(),greater<int>());
 
 for(i = 0; i < n; i++){
	 caz = 0;
	 contor = 0;
	if(v[i].inaltime <= h)
	{
	 kg.push_back(v[i].greutate);
	 push_heap(kg.begin(),kg.end(),greater<int>());
	 caz = 1;
	 contor = 1;
	 }
	 
	if(v[i].inaltime - u <= h && i!=0 && v[i].greutate > kg[0] && contor == 0 && (int)kg.size() > 0)
	{
		//cout<<"Ajunge"<<endl;
		
	   //int x = kg[0];	
	   //kg[0] = v[i].greutate;
	   //make_heap(kg.begin(),kg.end(),greater<int>());
	   //for(j = 0; j < kg.size() ;j++)
	   //{
		 // cout<<kg[j]<<" "<<endl;
		   
		 //}
		 //cout<<endl; 
	  // pop_heap(kg.begin(),kg.end());
	  //kg[0] = v[i].greutate;
	 // kg.push_back(v[i].greutate);
	 //push_heap(kg.begin(),kg.end(),greater<int>());
	   //for(j = 0; j < kg.size() ;j++)
	   //{
		 // cout<<kg[j]<<" "<<endl;
		   
		 //}
		// cout<<endl; 
	   // kg.erase(kg.begin(),kg.begin()+1);
	 //make_heap(kg.begin(),kg.end(),greater<int>());
	   //for(j = 0; j < kg.size() ;j++)
	   //{
		 // cout<<kg[j]<<" "<<endl;
		   
		 //}
		 //cout<<endl;
		 //for( j = 0; j < kg.size();j ++)
		 //{
			// cout<<kg[j]<<" "<<endl;
		  //}
		  //cout<<endl;		
		 
		 pop_heap(kg.begin(),kg.end(),greater<int>());
		 //for( j = 0; j < kg.size();j ++)
		 //{
			// cout<<kg[j]<<" "<<endl;
		  //}
		  //cout<<endl;				
		  kg.pop_back();
		  //for( j = 0; j < kg.size();j ++)
		 //{
			// cout<<kg[j]<<" "<<endl;
		  //}
		  //cout<<endl;	
		  kg.push_back(v[i].greutate);
	      push_heap(kg.begin(),kg.end(),greater<int>());
	    //  for( j = 0; j < kg.size();j ++)
		 //{
			// cout<<kg[j]<<" "<<endl;
		  //}
	}		  
	
	if(caz == 1){
		h = h- u;	 
	}
	
 }
 
 
 int s = 0;
 
 for(i = 0; i < (int)kg.size(); i++){
	 s = s + kg[i]; 
 }	 	 

  fout<<s;
  fin.close();
  fout.close();
  return 0;

 
}