Advertisement
Guest User

Untitled

a guest
Nov 20th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.71 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <math.h>
  3.  
  4. using namespace std;
  5.  
  6. int vals[100000];
  7. int memo[100000];
  8.  
  9. int solve(int k, int n, int vals[])
  10. {
  11. int ans;
  12.  
  13. if(n<0)
  14. return 0;
  15. else if(memo[n] == -1)
  16. {
  17. ans = vals[n] + solve(k, n-k-1, vals);
  18. for(int i = 1; i<=k; i++)
  19. ans = max(ans, solve(k, n-i, vals));
  20. memo[n] = ans;
  21. }
  22.  
  23. return memo[n];
  24. }
  25.  
  26. int main() {
  27. int n, k;
  28. cin >> n >> k;
  29. for(int i = 0; i < n; i++)
  30. cin >> vals[i];
  31. for(int j = 0; j < n; j++)
  32. memo[j] = -1;
  33. // solve and print answer here
  34. printf("%d", solve(k, n-1, vals));
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement