Advertisement
Josif_tepe

Untitled

Mar 18th, 2022
974
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <set>
  7. #include <cstring>
  8. #include <cmath>
  9. #include "cstring"
  10. using namespace std;
  11. int n,c;
  12. vector<pair<int ,int>> v;
  13. int memo[105][10005];
  14. int dp(int i,int coins_left){
  15.     if(i == -1){
  16.         return 0;
  17.     }
  18.     if(memo[i][coins_left] != -1){
  19.         return memo[i][coins_left];
  20.     }
  21.     int res = -500;
  22.     res = max(res,dp(i-1,coins_left));
  23.     if(coins_left - v[i].second >= 0){
  24.         res = max(res,dp(i-1,(coins_left -v[i].second)+ v[i].first)+1);
  25.     }
  26.     return  memo[i][coins_left] =res;
  27. }
  28. int main() {
  29.     ios_base::sync_with_stdio(false);
  30.  
  31.     cin >> n >> c;
  32.         for (int i = 0; i < c; i++) {
  33.         int a,b;
  34.         cin >> a >> b;
  35.         v.push_back(make_pair(b,a));
  36.     }
  37.     sort(v.begin(),v.end());
  38.     for (int i = 0; i < 105; i++) {
  39.         for (int j = 0; j < 10005; j++) {
  40.             memo[i][j] = -1;
  41.         }
  42.     }
  43.     cout << dp(c-1,n);
  44. }
  45.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement