fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. int n, k, z;
  6. long long dp[100005][10];
  7.  
  8. long long sol(int arr[], int pos, int total, int left) {
  9.  
  10. if (pos >= n || pos < 0 || total == 0) return 0;
  11. if (dp[pos][left] != -1) return dp[pos][left];
  12. long long ret = 0;
  13. if (pos < n)ret = max(ret, arr[pos] + sol(arr, pos + 1, total - 1, left));
  14.  
  15. if (left && pos > 0 && total) {
  16. ret = max(ret, sol(arr, pos - 1, total - 1, left - 1) + arr[pos]);
  17. }
  18.  
  19.  
  20. return dp[pos][left] = ret;
  21.  
  22. }
  23.  
  24.  
  25.  
  26. int main() {
  27. int cs;
  28. scanf("%d", &cs);
  29. while (cs--) {
  30. memset(dp, -1, sizeof(dp));
  31. scanf("%d %d %d", &n, &k, &z);
  32. int arr[n];
  33. for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
  34. long long ans = sol(arr, 1, k, z) + arr[0];
  35. printf("%lld\n", ans);
  36. }
  37. }
Success #stdin #stdout 0s 11460KB
stdin
4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9
stdout
15
19
150
56