#include using namespace std; using ll = long long; template istream& operator >> (istream& is, vector& vec) { for(T& x : vec) is >> x; return is; } template ostream& operator << (ostream& os, const vector& vec) { if(vec.empty()) return os; os << vec[0]; for(auto it = vec.begin(); ++it != vec.end(); ) os << ' ' << *it; return os; } /* 考察 00ではない区間をいい感じに忘れ去れる問題 01,10の区間で0の方 11の区間ならどちらでも可能 11の区間をどう使うかがミソ -> 2乗なので隣接のうち大きい方に付ければ良さそう 01 11 01 11 みたいなのときにどっちに付けて良いか分からなくないか... */ int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n; vector w(n); cin >> w >> m; vector s(m); cin >> s; vector ca; ca.reserve(n + m); w.insert(w.begin(), 0); for(int i = 0; i < n; i++)w[i + 1] += w[i]; ca.insert(ca.end(), w.begin(), w.end()); s.insert(s.begin(), 0); for(int i = 0; i < m; i++) s[i + 1] += s[i]; ca.insert(ca.end(), s.begin(), s.end()); sort(ca.begin(), ca.end()); ca.erase(unique(ca.begin(), ca.end()), ca.end()); int S = 0; vector> b; for(int i = 0, wi = 0, si = 0; i + 1 < ca.size(); i++){ int dt = ca[i + 1] - ca[i]; while(wi <= n && ca[i] == w[wi]){ wi++; S ^= 1; } while(si <= m && ca[i] == s[si]){ si++; S ^= 2; } b.emplace_back(dt, S); } // 1 - 3 - 1 // 2 - 3 - 2 // のように挟まれた3をマージする vector> c; c.emplace_back(b[0]); for(int i = 1; i < b.size(); i++){ if(b[i].second != 3){ c.emplace_back(b[i]); continue; } if(c.back().second == 0){ c.emplace_back(b[i]); continue; } if(i + 1 < b.size() && c.back().second == b[i + 1].second){ c.back().first += b[i].first + b[i + 1].first; i++; }else{ c.emplace_back(b[i]); } } vector dp(c.size() + 1); for(int i = 0; i < c.size(); i++){ auto [cnt, S] = c[i]; if(S == 0){ dp[i + 1] = max(dp[i + 1], dp[i]); continue; } dp[i + 1] = max(dp[i + 1], dp[i] + cnt * (ll)(cnt)); if(i + 1 < c.size()){ auto [cnt2, S2] = c[i + 1]; if(max(S, S2) != 3 || min(S, S2) == 0) continue; cnt += cnt2; dp[i + 2] = max(dp[i + 2], dp[i] + cnt * (ll)(cnt)); } } cout << dp.back() << '\n'; }