SHARE
TWEET

Untitled

a guest Feb 27th, 2020 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. typedef long long ll;
  7.  
  8. ll inf = 1e18;
  9.  
  10. int main() {
  11.     ios::sync_with_stdio(0);
  12.     cin.tie(0); cout.tie(0);
  13.     //freopen("input.txt", "r", stdin);
  14.     //freopen("output.txt", "w", stdout);
  15.     int w, n;
  16.     cin >> w >> n;
  17.     vector<pair<int,int>> a;
  18.     for(int i = 0; i < n; i++)
  19.     {
  20.         int c1, w1;
  21.         cin >> w1 >> c1;
  22.         a.push_back({w1,c1});
  23.     }
  24.     vector<int> dp(251);
  25.     dp[0] = 0;
  26.     for(int i = 1; i < w+1; i++)
  27.     {
  28.         for(int j = 0; j < n; j++)
  29.         {
  30.             if(i >= a[j].first)
  31.             {
  32.                 dp[i] = max(dp[i], a[j].second + dp[i - a[j].first] );
  33.             }
  34.         }
  35.     }
  36.     cout << dp[w];
  37.     return 0;
  38. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top