Card game

#include <bits/stdc++.h>
using namespace std;
// clang-format off
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { T value; is >> value; v.push_back(value); return is; }
#define preamble ios::sync_with_stdio(0); cin.tie(0); dbg("INIT");
// clang-format on
#ifdef DO_DBG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef set<ll> si;
typedef pair<ll, ll> pi;
typedef vector<pair<ll, ll>> vpi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
const int MAX_N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
#define loop(n) for (ll i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sq(x) ((x) * (x))

vi x;
ll n;
vb ready;
vi value;

int dp(ll l, ll r) {
  ll best = 0;
  if (r - l < 2) {
    return 0;
  }
  if (ready[l * (n + 1) + r])
    return value[l * (n + 1) + r];
  for (int i = l; i <= r - 2; i++) {
    auto sum1 = x[i + 1];
    ll lSum = dp(l, i - 1);
    ll rSum = dp(i + 3, r);
    best = max(best, sum1 + lSum + rSum);
  }
  ready[l * (n + 1) + r] = true;
  value[l * (n + 1) + r] = best;
  return best;
}

int main() {
  preamble;
  cin >> n;
  dbg(n);
  loop(n) cin >> x;
  dbg(n, x);
  ready.resize(sq(n + 1));
  value.resize(sq(n + 1));
  cout << dp(0, n - 1) << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: RUNTIME ERROR

Test 7

Verdict: RUNTIME ERROR

Test 8

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 9

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 10

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 15

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc