fork download
  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
stdin
10
10 71 84 33 6 47 23 25 52 64
stdout
36