#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
ll MOD = 1000000007;
const int SINF = 1000000009;
const ll INF = 1000000000000000018;
#define nl cout << "\n"
#define inv(a) powr((a), (MOD - 2))
#define all(c) (c).begin(),(c).end()
#define rep(i,a,b) for(ll i = (a); i < (b); i ++)
#define prec(n) cout << fixed << setprecision(n)
#define PI 3.14159265358979323846264338327951
#define ifalse ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
template<typename T> void toInt(string s, T &a) { istringstream(s) >> a; }
ll gcd(ll a, ll b) { ll t; while(a) { t = a; a = b%a; b = t; } return b; }
ll sub(ll a, ll b) { a -= b; a = (a + MOD) % MOD; return a; }
ll mul(ll a, ll b) { return ((a % MOD) * (b % MOD)) % MOD; }
ll add(ll a, ll b) { a += b; a %= MOD; return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll dp[100001][4][4];
int main()
{
ifalse;
ll t,n,temp;
const int D = 3;
cin >> t;
while(t--){
cin >> n;
vector<ll> a(n),b(n);
for(ll&x: a) cin >> x;
for(ll&x: b) cin >> x;
memset(dp,-1,sizeof(dp));
function<ll(int,int,int)> solve;
solve = [&](int i,int d1,int d2){
if(dp[i][d1][d2]!=-1) return dp[i][d1][d2];
if(i==n-1){
if(d1 && d2)
return max(a[i],b[i]);
else if(d1) return a[i];
else if(d2) return b[i];
else return 0LL;
}
if(d1 && d2){
dp[i][d1][d2] = max(a[i] + solve(i+1,d1-1,3), b[i] + solve(i+1,3,d2-1));
} else if(d1){
dp[i][d1][d2] = a[i] + solve(i+1,d1-1,3);
} else if(d2){
dp[i][d1][d2] = b[i] + solve(i+1,3,d2-1);
} else return 0LL;
return dp[i][d1][d2];
};
solve(0,3,3);
cout << dp[0][3][3];
nl;
}
return 0;
}
Language: C++