Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1653242) | Cod sursa (job #2375959) | Cod sursa (job #2793272)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ifstream in("lupu.in");
ofstream out("lupu.out");
int n, x, l;
in >> n >> x >> l;
vector<pair<int, int>> sheep(n);
for (int i = 0; i < n; ++i){
pair<int, int> p;
in >> p.first >> p.second;
sheep[i] = p;
}
sort(sheep.begin(), sheep.end(),
[](const pair<int, int> a, const pair<int, int> b) {
return a.first < b.first;
}
);
vector<vector<ll>> dp (n, vector<ll> (n+1));
for (int j = 0; j <= n; ++j){
if (sheep[0].first + j * l > x)
dp[0][j] = 0;
else
dp[0][j] = sheep[0].second;
}
for (int i = 1; i < n; ++i){
for (int j = 0; j <= n; ++j){
if (sheep[i].first + j * l > x)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max (dp[i-1][j], sheep[i].second + dp[i-1][j+1]);
}
}
out<< dp[n-1][0] << endl;
in.close();
out.close();
}
int main(){
solve();
return 0;
}