fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3.  
  4. #define fst first
  5. #define snd second 
  6.  
  7. typedef long long ll; 
  8. typedef pair<int, int> ii; 
  9.  
  10. const ll LINF = (ll)1e18; 
  11. const int INF = (int)1e9;
  12.  
  13. const int N = (int)5e3 + 5;  
  14.  
  15. // Giả sử có đoạn [l, r] là dãy 2-sum   
  16. // Tồn tại k: sum[k] - sum[l - 1] = sum[r] - sum[k] (l <= k <= r - 1)
  17. //        <=>    2 * sum[k]       = sum[r] + sum[l - 1] 
  18. //		  <=>      sum[k]         = (sum[r] + sum[l - 1]) / 2   
  19.  
  20. int n;   
  21. int a[N]; 
  22. ll sum[N];  
  23.  
  24. int main() {
  25. 	ios::sync_with_stdio(0); 
  26. 	cin.tie(0); 
  27. 	cin >> n;  
  28. 	for (int i = 1; i <= n; i++) {
  29. 		cin >> a[i]; 
  30. 		sum[i] = sum[i - 1] + a[i];  
  31. 	}
  32.  
  33. 	int ans = 0;   
  34. 	// O(n^2logn)
  35. 	for (int l = 1; l <= n; l++) {
  36. 		for (int r = l; r <= n; r++) {
  37. 			ll X = sum[r] + sum[l - 1];    
  38. 			if (X % 2 != 0) continue;   
  39. 			X /= 2;   
  40. 			int k = lower_bound(sum + l, sum + r, X) - sum;   
  41. 			if (k < r && sum[k] == X) ans = max(ans, r - l + 1);    
  42. 		}
  43. 	}
  44.  
  45. 	cout << ans << '\n';
  46. }
  47.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/aJMsPs
language:
C++14 (gcc 8.3)
created:
1 year 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!