Submission #19705827

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

void solve() {
  int n; cin >> n;
  vector<int> a(n);
  for(auto &x : a) cin >> x;

  vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
  int ans = 0;

  for(int k=0; k/3 < n/3; k+=3) {
    for(int i=0, j=k; j<=n; ++i, ++j) {
      for(int ni=i-3, nj=j; ni<=i; ++ni, ++nj) {
        if(0 <= ni && nj <= n) {
          int sum = 0;
          for(int l=ni; l<i; ++l) {
            sum += a[l];
          }
          for(int r=j; r<nj; ++r) {
            sum += a[r];
          }
          chmax(sum, 0);
          if(chmax(dp[ni][nj], dp[i][j] + sum)) {
            chmax(ans, dp[ni][nj]);
          }
        }
      }
    }
  }

  cout << ans << endl;
}

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  solve();
  return 0;
}

Submission Info

Judge Result