Advertisement
Saleh127

SPOJ LKS / DP

Nov 8th, 2021
770
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-08-13.16.00
  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.    ios_base::sync_with_stdio(0);
  15.    cin.tie(0);cout.tie(0);
  16.  
  17.  
  18.    ll n,m,i,j,k,l;
  19.  
  20.  
  21.    cin>>m>>n;
  22.  
  23.    ll v[n+4],w[n+4];
  24.  
  25.    for(i=0;i<n;i++)
  26.    {
  27.         cin>>v[i]>>w[i];
  28.    }
  29.  
  30.    ll dp[m+4]={0};
  31.  
  32.    dp[0]=1;
  33.  
  34.  
  35.    for(i=0;i<n;i++)
  36.    {
  37.         for(j=m;j>=w[i];j--)
  38.         {
  39.              dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
  40.         }
  41.    }
  42.  
  43.  
  44.    cout<<dp[m]<<nl;
  45.  
  46.    get_lost_idiot;
  47. }
  48.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement