fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. ////////////// Prewritten code follows. Look down for solution. ////////////////
  5.  
  6. #define fs first
  7. #define sc second
  8. #define pb push_back
  9. #define len(x) ((int)(x).size())
  10. #define all(x) (x).begin(), (x).end()
  11. #define rall(x) (x).rbegin(), (x).rend
  12. #define forn(i, n) for(int i = 0; i < (int)(n); ++i)
  13. #define for1(i, n) for(int i = 1; i <= (int)(n); ++i)
  14. #define ford(i, n) for(int i = (int)(n); i >= 0; --i)
  15. #define fore(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
  16.  
  17. typedef pair<int, int> pii;
  18. typedef vector<int> vi;
  19. typedef vector<pii> vpi;
  20. typedef vector<vi> vvi;
  21. typedef long long ll;
  22. typedef pair<ll, ll> pll;
  23. typedef vector<ll> vl;
  24. typedef vector<pll> vpl;
  25. typedef vector<vl> vvl;
  26.  
  27. template<typename T> void maxself(T &a, T &b){a = max(a, b);};
  28. template<typename T> void minself(T &a, T &b){a = min(a, b);};
  29.  
  30. const ll LINF = 1e18;
  31. const int INF = 1e9;
  32. const int MOD = 1e9+7;
  33.  
  34. /// command for char arrays with spaces -> scanf(" %[^\n]", text);
  35.  
  36. ////////////////////////// Solution starts below. //////////////////////////////
  37.  
  38. const int N = 4e5+5;
  39. int v[N];
  40.  
  41. struct Node{
  42. 	int prefixSum;
  43. 	int suffixSum;
  44. 	int totalSum;
  45. 	int maxSubArraySum;
  46. 	Node(){
  47. 		totalSum = 0;
  48. 		prefixSum = suffixSum = maxSubArraySum = -INF;
  49. 	}
  50. };
  51.  
  52. Node seg[4*N];
  53.  
  54. Node mergeNodes(Node l, Node r){
  55. 	Node ans;
  56. 	ans.totalSum = l.totalSum + r.totalSum;
  57. 	ans.prefixSum = max({0, l.prefixSum, l.totalSum + r.prefixSum});
  58. 	ans.suffixSum = max({0, r.suffixSum, r.totalSum + l.suffixSum});
  59. 	ans.maxSubArraySum = max({0, l.maxSubArraySum, r.maxSubArraySum, l.suffixSum + r.prefixSum, ans.prefixSum, ans.suffixSum, ans.totalSum});
  60. 	return ans;
  61. }
  62.  
  63. void build(int node, int l, int r){
  64. 	if(l == r){
  65. 		//folha
  66. 		seg[node].totalSum = v[l];
  67. 		seg[node].prefixSum = seg[node].suffixSum = seg[node].maxSubArraySum = max(0, v[l]);
  68. 	}else{
  69. 		int m = (l+r)>>1;
  70. 		build(2*node+1, l, m);
  71. 		build(2*node+2, m+1, r);
  72. 		seg[node] = mergeNodes(seg[2*node+1], seg[2*node+2]);
  73. 	}
  74. }
  75.  
  76. Node query(int node, int l, int r, int ql, int qr){
  77. 	if(qr < l or ql > r) return Node();
  78. 	if(ql <= l and qr >= r) return seg[node];
  79. 	int m = (l+r)>>1;
  80. 	return mergeNodes(query(2*node+1, l, m, ql, qr), query(2*node+2, m+1, r, ql, qr));
  81. }
  82.  
  83. int main(){
  84.  
  85. 	ios::sync_with_stdio(false);
  86. 	cin.tie(nullptr);
  87.  
  88. 	int n;
  89. 	cin >> n;
  90. 	for(int i = 0; i < n; i++){
  91. 		cin >> v[i];
  92. 	}
  93. 	for(int i = n; i < 2*n; i++){
  94. 		v[i] = v[i-n];
  95. 	}	
  96. 	build(0, 0, 2*n-1);
  97. 	Node ans = query(0, 0, 2*n-1, (n-1)>>1, (3*n-1)>>1);
  98. 	cout << ans.maxSubArraySum << endl;
  99. 	return 0;
  100. }
Success #stdin #stdout 0.01s 28644KB
comments (?)
stdin
copy 
2

-3 -10
stdout
copy 
0
https://ideone.com/CEGHD7
language:
C++14 (gcc 8.3)
created:
4 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!