説明のため \(A, B, C\) を 0-indexed に置き換えます。 以降、この解説において数列はすべて 0-indexed です。

\(A, B, C\) の累積和を取ります。すなわち、長さ \(N + 1\) の数列 \(D, E, F\) を \(\displaystyle D_i = \sum_{j = 0}^{i - 1} A_j, E_i = \sum_{j = 0}^{i - 1} B_j, F_i = \sum_{j = 0}^{i-1} C_j\) となるよう定めます。

最大化する対象 \(\displaystyle \sum_{i = 0} ^ {x - 1} A_i + \sum_{i = x}^{y - 1} B_i +\sum_ {i =y}^{N - 1} C_i\) を \(D, E, F\) を用いて書き直すと \(D_x - E_x + E_y - F_y + F_N\) となります。

\(F_N\) は \(x, y\) の選択によらない定数なので、目的は \(D_x - E_x + E_y - F_y\) を最大化することです。

数列 \(G, H\) を \(G_i = D_i - E_i, H_i = E_i - F_i\) により定めると、\(G_x + H_y\) を最大化すればよいです。これは、先頭から累積 max を取りながら \(y\) を全探索することによって実現できます。具体的には、数列 \(I\) を \(I_i = \displaystyle\max_{1 \leq j < i} G_j\) となるよう定めると、\(y\) を固定したときの最大値は \(I_y + H_y\) となります。

時間計算量は \(O(N)\) です。\(x = 0, x = y, y = N\) が許容されていないことに注意してください。

実装例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (n); i++)
const ll INF = 1000000000000000010;
template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; }

int main() {
	ll n;
	cin >> n;
	vector<ll> a(n), b(n), c(n);
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];
	rep(i, n) cin >> c[i];
	vector<ll> d(n + 1), e(n + 1), f(n + 1);
	rep(i, n) {
		d[i + 1] = d[i] + a[i];
		e[i + 1] = e[i] + b[i];
		f[i + 1] = f[i] + c[i];
	}
	vector<ll> g(n + 1), h(n + 1);
	rep(i, n + 1) {
		g[i] = d[i] - e[i];
		h[i] = e[i] - f[i];
	}
	ll mx = -INF;
	ll ans = 0;
	for (int j = 1; j < n; j++) {
		chmax(ans, mx + h[j] + f[n]);
		chmax(mx, g[j]);
	}
	cout << ans << '\n';
}