Saleh127

CSES 1158 / DP

Oct 28th, 2021 (edited)
167
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-28-20.46.09
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. int main()
  13. {
  14.  
  15.    int n,i,j,x;
  16.  
  17.    cin>>n>>x;
  18.  
  19.  
  20.    vector<vector<int>> dp(n+2,vector<int>(x+2));
  21.  
  22.    int price[n+2];
  23.    int page[n+2];
  24.  
  25.    for(i=0;i<n;i++) cin>>price[i];
  26.    for(i=0;i<n;i++) cin>>page[i];
  27.  
  28.    for(i=0;i<=n;i++)
  29.    {
  30.         for(j=0;j<=x;j++)
  31.         {
  32.              if(i==0)
  33.              {
  34.                   dp[i][j]=0;
  35.                   continue;
  36.              }
  37.  
  38.              dp[i][j]=dp[i-1][j];
  39.              if(j>=price[i-1])
  40.              {
  41.                   dp[i][j]=max(dp[i][j],dp[i-1][j-price[i-1]]+page[i-1]);
  42.              }
  43.         }
  44.    }
  45.  
  46.    cout<<dp[n][x]<<endl;
  47.  
  48.    get_lost_idiot;
  49. }
  50.  
RAW Paste Data