pastebin

Paste Search Dynamic
Recent pastes
dp
  1. #include <bits/stdc++.h>
  2. #define task ""
  3. #define endl 'n'
  4. #define MASK(i) (1LL << (i))
  5. #define c_bit(i) __builtin_popcountll(i)
  6. #define BIT(x, i) ((x) & MASK(i))
  7. #define SET_ON(x, i) ((x) | MASK(i))
  8. #define SET_OFF(x, i) ((x) &~ MASK(i))
  9. #define int long long
  10.  
  11. using namespace std;
  12.  
  13. const int oo=1e18;
  14.  
  15. int n,k;
  16. int a[500],b[500],f[200][200];
  17.  
  18. int dp(int id,int last)
  19. {
  20.     if (id > n)
  21.         return 0;
  22.     if (f[id][last] != -1)
  23.         return f[id][last];
  24.     int res = 0;
  25.     if (a[id] - a[last] >= k)
  26.         res = max(res,dp(id + 1,id) + b[id]);
  27.     res = max(res,dp(id + 1,last));
  28.     return f[id][last] = res;
  29. }
  30.  
  31. main()
  32. {
  33.     ios_base::sync_with_stdio(0);
  34.     cin.tie(0);cout.tie(0);
  35. //    freopen(task".inp","r",stdin);
  36. //    freopen(task".out","w",stdout);
  37.     memset(f,-1,sizeof f);
  38.     cin>>n>>k;
  39.     for (int i = 1;i <= n;i++)
  40.         cin>>a[i];
  41.     for (int i = 1;i <= n;i++)
  42.         cin>>b[i];
  43.     a[0] = -100;
  44.     cout<<dp(1,0);
  45.  
  46. }
Parsed in 0.005 seconds