# CFR Educational 17 D. Maximum path ( DP )

Problem - D - Codeforces

1 ≤ N ≤ 1e5
TL: 2000 ms
ML: 256 MB

dp[ i ][ j ]：準備從第幾行走出去，已考慮 j 列，此前提下最大總和

O( N )

```const int MAXN = 1e5;

int N;
int A[ 3 ][ MAXN ];
ll dp[ 3 ][ MAXN + 1 ];

void init(){
cin >> N;
for( int i = 0; i < 3; ++i ){
for( int j = 0; j < N; ++j ){
cin >> A[ i ][ j ];
}
}
}

void preprocess(){
for( int i = 0; i < 3; ++i ){
for( int j = 0; j <= N; ++j ){
dp[ i ][ j ] = - ( 1LL << 50 );
}
}
dp[ 0 ][ 0 ] = 0;
ll S0 = - ( 1LL << 50 ), S2 = - ( 1LL << 50 );
for( int i = 1; i <= N; ++i ){
upmax( dp[ 1 ][ i ], dp[ 1 ][ i - 1 ] + A[ 1 ][ i - 1 ] );
upmax( dp[ 1 ][ i ], dp[ 0 ][ i - 1 ] + A[ 0 ][ i - 1 ] + A[ 1 ][ i - 1 ] );
upmax( dp[ 1 ][ i ], dp[ 2 ][ i - 1 ] + A[ 2 ][ i - 1 ] + A[ 1 ][ i - 1 ] );
upmax( dp[ 0 ][ i ], dp[ 0 ][ i - 1 ] + A[ 0 ][ i - 1 ] );
upmax( dp[ 0 ][ i ], dp[ 1 ][ i - 1 ] + A[ 1 ][ i - 1 ] + A[ 0 ][ i - 1 ] );
upmax( dp[ 2 ][ i ], dp[ 2 ][ i - 1 ] + A[ 2 ][ i - 1 ] );
upmax( dp[ 2 ][ i ], dp[ 1 ][ i - 1 ] + A[ 1 ][ i - 1 ] + A[ 2 ][ i - 1 ] );
ll t = max( S0, S2 );
upmax( S0, max( t, dp[ 0 ][ i - 1 ] ) );
S0 += 1LL * A[ 0 ][ i - 1 ] + A[ 1 ][ i - 1 ] + A[ 2 ][ i - 1 ];
upmax( S2, max( t, dp[ 2 ][ i - 1 ] ) );
S2 += 1LL * A[ 2 ][ i - 1 ] + A[ 1 ][ i - 1 ] + A[ 0 ][ i - 1 ];
upmax( dp[ 2 ][ i ], S0 );
upmax( dp[ 0 ][ i ], S2 );
}
}

void solve(){
cout << dp[ 2 ][ N ] << endl;
}
```