Pagini recente » Cod sursa (job #1418633) | Cod sursa (job #2055468) | Cod sursa (job #3197172) | Cod sursa (job #2619144) | Cod sursa (job #2839801)
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
std::ifstream in("lupu.in");
std::ofstream out("lupu.out");
struct sheep{
int distance, wool;
};
std::vector<sheep> s;
std::priority_queue<int, std::vector<int>, std::greater<int>> q;
int main(){
int n, maxDist, leap;
in >> n >> maxDist >> leap;
for(int i=0; i<n; ++i){
int d, w;
in >> d >> w;
s.push_back({d, w});
}
std::sort(s.begin(), s.end(), [](const sheep &a, const sheep &b){
return a.distance > b.distance;
});
long long time = 0, woolQ = 0;
for(int i=0; i<n; ++i){
long long sheepDist = s[i].distance + time * leap;
if(sheepDist <= maxDist){
woolQ += s[i].wool;
q.push(s[i].wool);
++time;
}
else if(!q.empty() && s[i].wool > q.top()){
woolQ += s[i].wool - q.top();
q.pop();
q.push(s[i].wool);
}
}
out << woolQ;
}