Advertisement
Josif_tepe

Untitled

Mar 22nd, 2024
862
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. using namespace std;
  6. typedef long long ll;
  7. const int maxn = 1e5 + 1;
  8. const int INF = 2e9;
  9. int dp[1005][maxn];
  10.  
  11. int main() {
  12.     int n, x;
  13.     cin >> n >> x;
  14.    
  15.     vector<int> prices(n), pages(n);
  16.     for(int i = 0; i < n; i++) {
  17.         cin >> prices[i];
  18.     }
  19.     for(int i =0 ; i < n; i++) {
  20.         cin >> pages[i];
  21.     }
  22.    
  23.     for(int i = 0; i <= n; i++) {
  24.         for(int j = 0; j < maxn; j++) {
  25.             dp[i][j] = -INF;
  26.         }
  27.     }
  28.     dp[0][x] = 0;
  29.    
  30.     for(int at = 0; at < n; at++) {
  31.         for(int sum = x; sum >= 0; sum--) {
  32.             if(sum - prices[at] >= 0) {
  33.                 dp[at + 1][sum - prices[at]] = max(dp[at + 1][sum - prices[at]], dp[at][sum] + pages[at]);
  34.             }
  35.             dp[at + 1][sum] = max(dp[at + 1][sum], dp[at][sum]);
  36.         }
  37.     }
  38.     int res = -INF;
  39.     for(int sum = 0; sum <= x; sum++) {
  40.         res = max(res, dp[n][sum]);
  41.     }
  42.     cout << res << endl;
  43.     return 0;
  44. }
  45. //   2 1 3 3
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement