Untitled
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...)
#endif
int shape[][4] = {
{ 1, 1,
1, 0 },
{ 0, 1,
1, 1 },
{ 1, 1,
0, 1 },
{ 1, 0,
1, 1 }
};
void solve() {
int n;
cin >> n;
array<vector<int>, 2> b;
for(int i = 0, x; i < n; i++) {
cin >> x; b[0].push_back(x);
}
for(int i = 0, x; i < n; i++) {
cin >> x; b[1].push_back(x);
}
b[0].push_back(0);
b[1].push_back(0);
vector<array<int, 4>> dp(n + 1);
auto eval = [&](int i, int s[]) {
return b[0][i] * s[0] + b[0][i + 1] * s[1] +
b[1][i] * s[2] + b[1][i + 1] * s[3];
};
for(int i = 1; i <= n; i++) {
dp[i][0] = max(dp[i][0], dp[i - 1][0]);
dp[i][0] = max(dp[i][0], dp[i - 1][1]);
dp[i][0] = max(dp[i][0], dp[i - 1][2]);
dp[i][0] = max(dp[i][0], dp[i - 1][3]);
dp[i][1] = max(dp[i][1], dp[i - 1][0] + eval(i - 1, shape[0]));
dp[i][2] = max(dp[i][2], dp[i - 1][0] + eval(i - 1, shape[3]));
dp[i][3] = max(dp[i][3], dp[i - 1][0] + eval(i - 1, shape[1]));
dp[i][3] = max(dp[i][3], dp[i - 1][1] + eval(i - 1, shape[1]));
dp[i][3] = max(dp[i][3], dp[i - 1][0] + eval(i - 1, shape[2]));
dp[i][3] = max(dp[i][3], dp[i - 1][2] + eval(i - 1, shape[2]));
}
cout << dp[n][0] << endl;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
Cpp
INFO