fork download
copy 
  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4. using namespace std;
  5. typedef long long ll;
  6.  
  7. vector<ll> arr;
  8. pair<int, int> picked[301][301];
  9. int n, m;
  10. ll table[301][301];
  11. ll solve(int i, int e)
  12. {
  13. 	if (e == 1)
  14. 	{
  15. 		ll ret = 0;
  16. 		for (int j = i; j < n; j++)
  17. 			ret += arr[j];
  18. 		picked[i][e] = make_pair(n-i, -1);
  19. 		return ret;
  20.  
  21. 	}
  22. 	if (i >= n)
  23. 		return 99999;
  24. 	if (e < 0)
  25. 		return 0;
  26. 	ll currVal = arr[i];
  27. 	if (table[i][e] != -1)
  28. 		return table[i][e];
  29. 	ll &ret = table[i][e] = 99999999;
  30. 	for (int j = i + 1; j < n; j++)
  31. 	{
  32. 		if (ret >= max(currVal, solve(j, e - 1)))
  33. 			picked[i][e] = make_pair(j - i, j);
  34. 		ret = min(ret, max(currVal, solve(j, e - 1)));
  35. 		currVal += arr[j];
  36. 	}
  37. 	return ret;
  38. }
  39. int construct(int i,int e)
  40. {
  41. 	auto x = picked[i][e];
  42. 	if (x.first == -1 && x.second == -1)
  43. 		return 0;
  44. 	cout << x.first << ' ';
  45. 	construct(x.second, e - 1);
  46. 	return 0;
  47. }
  48. int main()
  49. {
  50. 	for (int i = 0; i < 301;i++)
  51. 	for (int j = 0; j < 301; j++)
  52. 		table[i][j] = -1;
  53. 	cin >> n >> m;
  54. 	arr.resize(n);
  55. 	for (auto &i : arr)
  56. 		cin >> i;
  57. 	cout<<solve(0, m) << endl;
  58. 	construct(0, m);
  59. 	cout << endl;
  60. }
  61.  
Success #stdin #stdout 0s 4880KB
comments (?)
stdin
copy 
8 3
5 4 2 6 9 3 8 7
stdout
copy 
17
4 2 2
https://ideone.com/S1RjzD
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

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!