fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits.h>
  4. using namespace std;
  5.  
  6. int sum[190][90][3];
  7.  
  8. int solution(vector<int> &arr, int l, int k, int p){
  9. if(sum[l][k][p]){
  10. return sum[l][k][p];
  11. }
  12. int ans = 0;
  13. if(arr.size() - l <= k){
  14. for(int i = l; i < arr.size(); i++){
  15. ans += arr[i];
  16. }
  17. if(p == 2){
  18. sum[l][k][p] = 0;
  19. return sum[l][k][p];
  20. }
  21. sum[l][k][p] = ans;
  22. return sum[l][k][p];
  23. }
  24. if(p == 1){
  25. int temp = 0;
  26. for(int i = 1; i <= k; i++){
  27. temp += arr[(l-1) + i];
  28. ans = max(ans, temp + solution(arr, l+i, i, 3-p));
  29. }
  30. sum[l][k][p] = ans;
  31. return sum[l][k][p];
  32. }
  33. else{
  34. int ans = INT_MAX;
  35. for(int i = 1; i <= k; i++){
  36. ans = min(ans, solution(arr, l+i, i, 3-p));
  37. }
  38. sum[l][k][p] = ans;
  39. return sum[l][k][p];
  40. }
  41. }
  42.  
  43. int main() {
  44. int n, k, a;
  45. vector<int> coins;
  46. cin >> n;
  47. for(int i = 0; i < n; i++){
  48. cin >> a;
  49. coins.push_back(a);
  50. }
  51. cin >> k;
  52. cout << solution(coins, 0, k, 1);
  53. return 0;
  54. }
Success #stdin #stdout 0s 15440KB
stdin
14  76 112 3 1 98 4 172 33 65 90 2 71 18 32  14
stdout
777