fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll NEG_INF = -(ll)4e18;
  5.  
  6. int main(){
  7. ios::sync_with_stdio(false);
  8. cin.tie(nullptr);
  9.  
  10. int n, k, x;
  11. cin >> n >> k >> x;
  12. vector<ll> a(n+1);
  13. for(int i = 1; i <= n; i++)
  14. cin >> a[i];
  15.  
  16. // dp[i][j] = max sum using exactly j picks, with the j-th pick at position i
  17. static ll dp[201][201];
  18. for(int i = 0; i <= n; i++)
  19. for(int j = 0; j <= x; j++)
  20. dp[i][j] = NEG_INF;
  21.  
  22. dp[0][0] = 0; // “0 picks, ending at position 0” = 0 sum
  23.  
  24. // Build up
  25. for(int i = 1; i <= n; i++){
  26. for(int j = 1; j <= x; j++){
  27. ll bestPrev = NEG_INF;
  28. // Try picking a[i] as the j-th repost, previous pick was at t = i - d
  29. for(int d = 1; d <= k && i - d >= 0; d++){
  30. bestPrev = max(bestPrev, dp[i - d][j - 1]);
  31. }
  32. if(bestPrev > NEG_INF)
  33. dp[i][j] = bestPrev + a[i];
  34. }
  35. }
  36.  
  37. // Now your last pick must be within the last k positions: i in [n-k+1 .. n]
  38. ll ans = NEG_INF;
  39. for(int i = n - k + 1; i <= n; i++){
  40. ans = max(ans, dp[i][x]);
  41. }
  42. if(ans < 0) ans = -1;
  43. cout << ans << "\n";
  44. return 0;
  45. }
  46.  
Success #stdin #stdout 0.01s 5288KB
stdin
5 2 3
5 1 3 10 1
stdout
18