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()

vi x;
int dp(ll l, ll r) {
  ll best = 0;
  if (r - l < 2) {
    return 0;
  }
  for (int i = l; i <= r - 2; i++) {
    auto sum1 = x[i + 1];
    dbg("Combining", x[i], x[i + 1], x[i + 2], "into", sum1);
    ll l2 = l, r2 = i - 1;
    ll lSum = 0, rSum = 0;
    if (r2 - l2 >= 2) {
      dbg(l, r, "Calling with", l2, r2);
      lSum = dp(l2, r2);
    }
    l2 = i + 3;
    r2 = r;
    if (r2 - l2 >= 2) {
      dbg(l, r, "Calling with", l2, r2);
      rSum = dp(l2, r2);
    }
    best = max(best, sum1 + lSum + rSum);
  }
  return best;
}

int main() {
  preamble;
  ll n;
  cin >> n;
  dbg(n);
  loop(n) cin >> x;
  dbg(n, x);
  cout << dp(0, n - 1) << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: TIME LIMIT EXCEEDED

Test 15

Verdict: TIME LIMIT EXCEEDED