Guest User

Untitled

a guest
Jun 16th, 2020
86
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. using llong = long long;
  5. llong max_earning()
  6. {
  7.     int N, K;
  8.     cin >> N >> K;
  9.  
  10.     vector<llong> A(N), B(N);
  11.  
  12.     for (int i = 0; i < N; i++)
  13.         cin >> A[i] >> B[i];
  14.  
  15.     int fb_size = *max_element(begin(A), end(A));
  16.  
  17.     vector<llong> memofb(fb_size + 1, -1);
  18.     function<llong(llong)> fb = [&](llong i)->llong {
  19.         if (i == 0 || i == 1)
  20.             return 1;
  21.         if (memofb[i] != -1)
  22.             return memofb[i];
  23.         return memofb[i] = fb(i - 1) + fb(i - 2);
  24.     };
  25.  
  26.     vector<llong> memo(K + 1, -1);
  27.     function<llong(llong)> dp = [&](llong l)->llong {
  28.         if (l == 0)
  29.             return 0;
  30.  
  31.         if (memo[l] != -1)
  32.             return memo[l];
  33.  
  34.         llong p = 0;
  35.         for (int i = 0; i < N; i++)
  36.             if(l - fb(A[i]) >= 0)
  37.                 p = max(p, dp(l - fb(A[i])) + B[i]);
  38.  
  39.         return memo[l] = p;
  40.     };
  41.  
  42.     return dp(K);
  43. }
  44.  
  45. int main()
  46. {
  47.     int T;
  48.     cin >> T;
  49.     vector<int> V;
  50.     for (int i = 0; i < T; i++)
  51.         cout << max_earning() << "\n";
  52. }
RAW Paste Data