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