fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define rep(i, a, b) for(int i = a; i < (b); ++i)
  6. #define all(x) begin(x), end(x)
  7. #define sz(x) (int)(x).size()
  8. #define pb push_back
  9. typedef long long ll;
  10. typedef pair<int, int> pii;
  11. typedef vector<int> vi;
  12.  
  13. mt19937 rng;
  14.  
  15. ll part(vector<int> a) {
  16.     int N = sz(a);
  17.     ll sum = 0;
  18.     for (int i : a) sum += i;
  19.     vector<ll> pre;
  20.     ll cur = 0, res = -1;
  21.     for (int i = 0; i < N; i++) {
  22.         ll x = sum - cur;
  23.         if (i >= 2) {
  24.             if (cur >= 2 * x) {
  25.                 int j = lower_bound(all(pre), 2 * x) - pre.begin();
  26.                 assert(pre[j] >= 2 * x);
  27.                 if (cur - pre[j] >= 2 * pre[j]) {
  28.                     res = max(res, x);
  29.                 }
  30.             }
  31.             if (pre[0] <= cur - 2 * x) {
  32.                 int j = lower_bound(all(pre), cur - 2 * x + 1) - pre.begin() - 1;
  33.                 assert(cur - pre[j] >= 2 * x);
  34.                 if (pre[j] >= 2 * (cur - pre[j])) {
  35.                     res = max(res, x);
  36.                 }
  37.             }
  38.             int j = lower_bound(all(pre), (2 * cur + 2) / 3) - pre.begin();
  39.             if (j + 1 < i && x >= 2 * pre[j]) {
  40.                 res = max(res, cur - pre[j]);
  41.             }
  42.         }
  43.         cur += a[i];
  44.         pre.pb(cur);
  45.     }
  46.     return res;
  47. }
  48.  
  49. void solve() {
  50.     int N; cin >> N;
  51.     assert(3 <= N && N <= 100000);
  52.     vector<int> a(N);
  53.     for (int i = 0; i < N; i++) cin >> a[i], assert(1 <= a[i] && a[i] <= 1000000000);
  54.     ll res = part(a);
  55.     reverse(all(a));
  56.     res = max(res, part(a));
  57.     cout << res << "\n";
  58. }
  59.  
  60. int main() {
  61.     ios::sync_with_stdio(false);
  62.     cin.tie(nullptr);
  63.     rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
  64.  
  65.     solve();
  66.  
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4
2 1 1 3
stdout
copy 
1
https://ideone.com/KJ4q1N
language:
C++ (gcc 8.3)
created:
4 hours 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!