Submission #3664571

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define yes(f) cout<<((f)?"Yes\n":"No\n")

template< typename A >
void pr(A a) { cout << a << endl; }

template< typename A, typename B >
void pr(A a, B b) { cout << a << " " << b << endl; }

template< typename A >
void PR(A a) {
  rep(i, a.size()) {
    if(i) cout << ' ';
    cout << a[i];
  }
  cout << endl;
}

using int64 = long long;
const int64 LINF = 1LL << 60;
const int INF = (1 << 30) - 1;
const int mod = (int) (1e9 + 7);
using pi = pair< int, int >;

// -------------------------------- //


int N, A[1000];
int64 dp[2][1001];

inline int64 check2(int64 v, int idx, int f) {
  if(idx == N) return 0;
  if(~dp[idx][f]) return dp[idx][f];

  int64 ret = f ? -LINF : LINF;

  int64 sum = 0LL;
  for(int i = idx; i < N; i++) {
    sum += A[i];
    if((f && sum >= v) || (!f && sum < v)) {
      if(f) ret = max(ret, check2(v, i + 1, f ^ 1) + 1);
      else ret = min(ret, check2(v, i + 1, f ^ 1) - 1);
    } else {
      if(f) ret = max(ret, check2(v, i + 1, f ^ 1) - 1);
      else ret = min(ret, check2(v, i + 1, f ^ 1) + 1);
    }
  }
  return dp[idx][f] = ret;
}

int main() {

  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];

  auto check = [&](int64 v) {
    for(int i = 0; i <= 1000; i++) dp[0][i] = -INF;
    for(int i = 0; i <= 1000; i++) dp[1][i] = INF;
    dp[1][N] = 0;
    dp[0][N] = 0;
    for(int i = N - 1; i >= 0; i--) {
      int64 sum = 0;
      for(int j = i + 1; j <= N; j++) {
        sum += A[j - 1];
        dp[0][i] = max(dp[0][i], dp[1][j] + (sum >= v ? 1 : -1));
        dp[1][i] = min(dp[1][i], dp[0][j] + (sum >= v ? 1 : -1));
      }
    }
    return dp[0][0] >= 0;
  };

  int64 ok = -(1LL << 40), ng = 1LL << 40;
  while(ng - ok > 1) {
    int64 mid = (ok + ng) / 2;
    if(check(mid)) ok = mid;
    else ng = mid;
  }
  cout << ok << endl;
}

Submission Info

Judge Result