Solution #
The problem would be a standard dp problem if we can’t go to the left. So we need to handle that extra case. However, we can observe that we don’t need to go more than one cell to the left. Here is a quick proof:
So we only need to consider two more transition. Here is all the transition:
Code #
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template<typename... T> void rd(T&... args) {((cin>>args), ...);}
template<typename... T> void wr(T... args) {((cout<<args<<" "), ...);cout<<endl;}
void inline cmax(ll& a,ll b){
if(b>a) a=b;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<vector<ll>> a(n+2,vector<ll>(3)),dp(n+2,vector<ll>(3,-1e18));
forn(j,3) for1(i,n) cin>>a[i][j];
dp[0][0]=0;
for(int i=1;i<=n;i++){
cmax(dp[i][0],max({dp[i-1][0],dp[i-1][1]+a[i][1],dp[i-1][2]+a[i][1]+a[i][2]})+a[i][0]);
cmax(dp[i][1],max({dp[i-1][0]+a[i][0],dp[i-1][1],dp[i-1][2]+a[i][2]})+a[i][1]);
cmax(dp[i][2],max({dp[i-1][0]+a[i][0]+a[i][1],dp[i-1][1]+a[i][1],dp[i-1][2]})+a[i][2]);
cmax(dp[i+1][0],dp[i-1][2]+a[i][0]+a[i][1]+a[i][2]+a[i+1][0]+a[i+1][1]+a[i+1][2]);
cmax(dp[i+1][2],dp[i-1][0]+a[i][0]+a[i][1]+a[i][2]+a[i+1][0]+a[i+1][1]+a[i+1][2]);
}
cout<<dp[n][2];
return 0;
}