| 26 | ostream &operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) { cout << it << " "; } return ostream; } |
| 27 | |
| 28 | void solve() { |
| 29 | int n, x; cin >> n >> x; |
| 30 | vector<int> cost(n); cin >> cost; |
| 31 | vector<int> weight(n); cin >> weight; |
| 32 | vector<vector<int>> dp(n+1,vector<int> (x+1,-1)); |
| 33 | |
| 34 | for (int i = 0; i <= x; ++i) { |
| 35 | if (i >= cost[0]) { |
| 36 | dp[0][i] = weight[0]; |
| 37 | } else dp[0][i] = 0; |
| 38 | } |
| 39 | |
| 40 | for (int i = 1; i < n; ++i) { |
| 41 | for (int tar = 1; tar <=x; ++tar) { |
| 42 | int notake = dp[i-1][tar]; |
| 43 | int take = 0; |
| 44 | if (tar >= cost[i]) take = dp[i-1][tar-cost[i]] + weight[i]; |
| 45 | dp[i][tar] = max(take,notake); |
| 46 | } |
| 47 | } |
| 48 | cout << dp[n-1][x]; |
| 49 | } |
| 50 | |
| 51 | signed main() { |
| 52 | ios_base::sync_with_stdio(false),cin.tie(nullptr); |