Cod sursa(job #439103)

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

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

 
}