Cod sursa(job #439564)

Utilizator mihai.popescuPopescu Mihai mihai.popescu Data 11 aprilie 2010 17:05:04
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 1.87 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,j;
 
 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(kg.size() > 0)
	 //cout<<"Aici:"<<v[i].inaltime<<" "<<u<<" "<<h<<" "<<v[i].greutate<<" "<<kg[0]<<endl; 
	if(v[i].inaltime <= h)
	{
	 kg.push_back(v[i].greutate);
	 push_heap(kg.begin(),kg.end(),greater<int>());
	 //make_heap(kg.begin(),kg.end(),greater<int>());
	 caz = 1;
	//cout<<"Intra "<<i<<endl;
	 contor = 1;
	  //for(j = 0; j < kg.size(); j++)
	   //cout<<kg[j]<<" ";
	   //cout<<endl;	
	 }
	 
	if(v[i].inaltime - u <= h && i!=0 && v[i].greutate > kg[0] && contor == 0 && (int)kg.size() > 0)
	{
		//pop_heap(kg.begin(),kg.end());
		//kg.push_back(v[i].greutate);
	    //push_heap(kg.begin(),kg.end(),greater<int>());
	    kg[0] = v[i].greutate;
	    make_heap(kg.begin(),kg.end(),greater<int>());
	// cout<<"Intra2 "<<i<<endl;
	}		  
	
	if(caz == 1){
		//for(j = i+1; j < n ; j++)
		//{
			//v[j].inaltime = v[j].inaltime + u;	
		//}
		h = h- u;	 
	}
	
 }
 //for(j = 0; j < kg.size(); j++)
	//	cout<<kg[j]<<" ";
	//cout<<endl;	
 
 int s = 0;
 //cout<<kg.size()<<endl;
 
 for(i = 0; i < (int)kg.size(); i++){
	 s = s + kg[i]; 
 }	 	 

// cout<<s<<endl;
  fout<<s;
  fin.close();
  fout.close();
  return 0;

 
}