fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<int,int> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. ll dp[10001][10001];
  25. int n; 
  26. ll a[10001];
  27. ll s[10001];
  28.  
  29. ll sum(int l, int r)
  30. {
  31. 	if(l>r) return 0;
  32. 	if(l==0) return s[r];
  33. 	else return s[r]-s[l-1];
  34. }
  35.  
  36. int main()
  37. {
  38. 	ios_base::sync_with_stdio(0); cin.tie(0);
  39. 	cin>>n;
  40. 	for(int i = 0; i < n; i++)
  41. 	{
  42. 		cin>>a[i];
  43. 		s[i]=a[i];
  44. 		if(i>0) s[i]+=s[i-1];
  45. 		dp[1][i] = s[i];
  46. 	}
  47. 	for(int i = 2; i <= n; i++)
  48. 	{
  49. 		int opt = i - 1;
  50. 		for(int j = i - 1; j < n; j++)
  51. 		{
  52. 			ll ans = max(dp[i-1][opt-1], sum(opt,j));
  53. 			while(opt+1<=j&&max(sum(opt+1,j),dp[i-1][opt])<=ans)
  54. 			{
  55. 				ans = max(sum(opt+1,j),dp[i-1][opt]);
  56. 				opt++;
  57. 			}
  58. 			dp[i][j] = ans;
  59. 		}
  60. 	}
  61. 	for(int i = 1; i <= n; i++)
  62. 	{
  63. 		cout << dp[i][n-1] << ' ';
  64. 	}
  65. }
  66.  
Success #stdin #stdout 0s 796672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WPQm30
language:
C++14 (gcc 8.3)
created:
7 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!