Pagini recente » Cod sursa (job #1097685) | Cod sursa (job #2503016) | Cod sursa (job #263331) | Cod sursa (job #385517) | Cod sursa (job #2877451)
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
map <int, long long> dp;
struct Sheep {
int time;
int wool;
};
bool compareSheep(Sheep a, Sheep b) {
if(a.time == b.time){
return (a.wool > b.wool);
}
return (a.time < b.time);
}
int const NMAX = 1e5;
Sheep herd[1 + NMAX];
int main() {
int n, x, l;
long long ans = 0;
in >> n >> x >> l;
for(int i = 1;i <= n;i++) {
int dist, wool;
in >> dist >> wool;
int time = (x - dist) / l + 1;
herd[i].time = time;
herd[i].wool = wool;
}
sort(herd+1, herd+n+1, compareSheep);
for(int i = 1;i <= n;i++) {
if(herd[i].time != 0) {
auto it = dp.upper_bound(-herd[i].time);
if(it == dp.end()) {
if(it == dp.end()){
dp[-1] = max(1LL * herd[i].wool, 1LL * dp[-1]);
//cout << dp[-1] << ' ';
ans = max(ans, dp[-1]);
}
}else {
if(it == dp.end()){
//cout << "it->first = 0\n";
dp[-1] = max(1LL * herd[i].wool, 1LL * dp[-1]);
//cout << dp[-1] << ' ';
ans = max(ans, dp[-1]);
}else {
//cout << "it->first = "<< it->first << '\n';
dp[it->first - 1] = max(dp[it->first - 1], it->second + herd[i].wool);
//cout << dp[it->first - 1] << ' ';
ans = max(ans, dp[it->first - 1]);
}
}
}
}
out << ans << '\n';
return 0;
}