Cod sursa(job #441095)
#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;
}