Untitled

Run Settings
LanguageC++
Language Version
Run Command
#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(); } }
Editor Settings
Theme
Key bindings
Full width
Lines