Submission #2874989

---

Source Code Expand

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647;
const long long int llINF = 9223372036854775807;

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using edge = struct {
  int to;
  int cost;
};
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i, n, m) for (ll i = (n); i < (m); i++)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define MAXI(vec)                                                              \
  std::distance(vec.begin(), *std::max_element(vec.begin(), vec.end()))
#define MINI(vec)                                                              \
  std::distance(vec.begin(), *std::min_element(vec.begin(), vec.end()))

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

template <typename T, typename U> U READ(ll V, T a, U b) {
  REP(i, V) {
    cin >> a;
    b.push_back(a);
  }
  return b;
}

int main() {
  ll N = 0;
  vector<ll> A;
  vector<unsigned long long int> B;
  unsigned long long int sum = 0;
  ll po = 0;
  cin >> N;
  REP(i, N) {
    cin >> po;
    A.push_back(po);
    sum += po;
    B.push_back(sum);
  }
  ll mi = llINF;
  FOR(i, 1, N - 1) {
    ll left = B[i];
    ll right = B[N - 1] - B[i];
    ll lh = left / 2, rh = right / 2;
    ll l1 = lower_bound(B.begin(), B.begin() + i, lh) - B.begin();
    ll l2 = lower_bound(B.begin() + i + 1, B.end(), left + rh) - B.begin();
    ll w[2] = {0, -1};
    REP(k, 4) {
      vector<ll> pa(4);
      pa[0] = B[l1 + w[k % 2]];
      pa[1] = B[i] - B[l1 + w[k % 2]];
      pa[2] = B[l2 + w[k / 2]] - B[i];
      pa[3] = B[N - 1] - B[l2 + w[k / 2]];
      if (MIN(pa) == 0 || (l1 == 0 && k % 2 == 1) || (l1 == i && k % 2 == 0) ||
          (l2 == i + 1 && k / 2 == 1) || (l2 == N - 1 && k / 2 == 0)) {
        continue;
      }
      mi = min(mi, MAX(pa) - MIN(pa));
    }
  }
  cout << mi << endl;

  return 0;
}

Submission Info

Judge Result