fork(3) download
copy 
  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
comments (?)
stdin
copy 
14  76 112 3 1 98 4 172 33 65 90 2 71 18 32  14
stdout
copy 
777
https://ideone.com/rKUc1h
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!