Paste Search Dynamic
memset
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. int main() {
  5.         int s,n;cin>>s>>n;
  6.         long long dp[n+1][s+1];
  7.         memset(dp,0,sizeof(dp));
  8.         ll w[n+1],val[n+1];
  9.         for(int i=0;i<n;i++){
  10.                 cin>>w[i];
  11.                 cin>>val[i];
  12.         }
  13.         for(int i=0;i<=n;i++){
  14.                 for(int j=0;j<=s;j++){
  15.                         if(i==0 || j==0) dp[i][j]=0;
  16.                         else if(w[i-1]<=j){
  17.                                 dp[i][j]=max(val[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]);
  18.  
  19.                         }
  20.                         else dp[i][j]=dp[i-1][j];
  21.                 }
  22.         }
  23.         cout<<dp[n][s]<<"\n";
  24.         return 0;
  25. }
  26.  
Parsed in 0.004 seconds