fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. signed main() {
  5. 	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. 	int n; cin >> n;
  7. 	vector<int> a(n);
  8. 	for (int i = 0; i < n; i++) cin >> a[i];
  9. 	vector<vector<int>> pre(n, vector<int>(2)), suf(n, vector<int>(2));
  10. 	pre[1][0] = a[0], pre[1][1] = a[1];
  11. 	int left = a[0], right = a[1];
  12. 	int l = 0;
  13. 	for (int i = 2; i < n; i++) {
  14. 		right += a[i];
  15. 		int cur = abs(right - left);
  16. 		while (l + 1 < i && cur >= abs((right - a[l + 1] - (left + a[l + 1])))) {
  17. 			l++;
  18. 			right -= a[l];
  19. 			left += a[l];
  20. 			cur = abs(right - left);
  21. 		}
  22. 		pre[i][0] = left;
  23. 		pre[i][1] = right;
  24. 	}
  25. 	suf[n - 2][0] = a[n - 2];
  26. 	suf[n - 2][1] = a[n - 1];
  27. 	left = a[n - 2], right = a[n - 1];
  28. 	int r = n - 1;
  29. 	for (int i = n - 3; i >= 2; i--) {
  30. 		left += a[i];
  31. 		int cur = abs(left - right);
  32. 		while (r - 1 > i && cur >= abs(right + a[r - 1] - (left - a[r - 1]))) {
  33. 			r--;
  34. 			left -= a[r];
  35. 			right += a[r];
  36. 			cur = abs(left - right);
  37. 		}
  38. 		suf[i][0] = left;
  39. 		suf[i][1] = right;
  40. 	}
  41. 	int ans = 1e18;
  42. 	for (int i = 1; i < n - 2; i++) {
  43. 		vector<int> cur;
  44. 		cur.push_back(pre[i][0]);
  45. 		cur.push_back(pre[i][1]);
  46. 		cur.push_back(suf[i + 1][0]);
  47. 		cur.push_back(suf[i + 1][1]);
  48. 		sort(cur.begin(), cur.end());
  49. 		ans = min(ans, abs(cur[0] - cur.back()));
  50. 	}
  51. 	cout << ans << '\n';
  52.  
  53. }
Success #stdin #stdout 0s 5436KB
comments (?)
stdin
copy 
10
10 71 84 33 6 47 23 25 52 64
stdout
copy 
36
https://ideone.com/vU8Ea2
language:
C++14 (gcc 8.3)
created:
3 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!