Overview

This is a problem where you start somewhere at the mountain peak and descend to the base, moving to the next row while maximizing the total score.
However, since you cannot make two consecutive moves in the left direction or two consecutive moves in the right direction, we solve this using dynamic programming that remembers “which direction we moved in the previous step.”

Analysis

From each row to the next row, you can change your column by:

• \(-1\) (move left)
• \(0\) (move straight)
• \(+1\) (move right)

The constraint is that, for example:

• Moving left immediately after moving left
• Moving right immediately after moving right

is not allowed.

On the other hand, after moving straight, you can move left, straight, or right next.

Simply having

\(dp[i][j] =\) maximum score when reaching row \(i\), column \(j\)

is insufficient.

This is because depending on whether the path achieving that maximum score “came from a left move” or “came from a right move,” the available moves for the next step change.

For example, even if you reach the same cell with the same score:

• If the previous move was left, you cannot move left next
• If the previous move was right, you cannot move right next
• If the previous move was straight, you can move in any direction next

These differences exist.

Therefore, for each cell, we separate states by “the direction of the previous move.”

Algorithm

For the currently processed row, we maintain the following \(3\) types of DP:

• \(dpL[j]\): maximum score when at column \(j\) of the current row, with the previous move being a left move
• \(dpS[j]\): maximum score when at column \(j\) of the current row, with the previous move being a straight move
• \(dpR[j]\): maximum score when at column \(j\) of the current row, with the previous move being a right move

Here, column indices are \(0\)-indexed in the code.

At row \(1\), no move has been made yet.
Therefore, for convenience, we treat it as if we “came by moving straight,” and set:

\[ dpS[j] = G_{1,j} \]

---

Consider the case of reaching column \(j\) of the next row.

Moving straight

We come from column \(j\) of the previous row.

Moving straight is possible regardless of the previous move direction.

Therefore,

\[ ndpS[j] = \max(dpL[j], dpS[j], dpR[j]) + G_{i,j} \]

Moving left

Arriving at column \(j\) by a left move means we were at column \(j+1\) in the previous row.

However, if the previous move was also a left move, this would result in left-left, which is forbidden.

Therefore, only \(dpS[j+1]\) or \(dpR[j+1]\) can be used as the previous state.

\[ ndpL[j] = \max(dpS[j+1], dpR[j+1]) + G_{i,j} \]

This applies only when \(j+1\) is within the grid bounds.

Moving right

Arriving at column \(j\) by a right move means we were at column \(j-1\) in the previous row.

However, if the previous move was also a right move, this would result in right-right, which is forbidden.

Therefore, only \(dpS[j-1]\) or \(dpL[j-1]\) can be used as the previous state.

\[ ndpR[j] = \max(dpS[j-1], dpL[j-1]) + G_{i,j} \]

This applies only when \(j-1\) is within the grid bounds.

---

We perform this transition for each row, and after processing up to the last row, the answer is the maximum value across all columns and all states of the last row.

\[ \max_j \max(dpL[j], dpS[j], dpR[j]) \]

Complexity

• Time complexity: \(O(NM)\)
• Space complexity: \(O(M)\)

Since we perform a constant number of transitions per cell, the time complexity is \(O(NM)\).

Also, since the DP can be updated using only the information from the previous row, there is no need to store the entire grid or DP values for all rows.
Therefore, the space complexity is \(O(M)\).

Implementation Notes

The score can potentially be as large as

\[ 2 \times 10^6 \times 10^9 = 2 \times 10^{15} \]

This exceeds the range of int, so long long must be used.

Also, we prepare a sufficiently small value NEG_INF to represent unreachable states.

const long long NEG_INF = -(1LL << 60);

Conditional checks are also needed to avoid moving to columns outside the bounds:

if (j + 1 < M)

and

if (j - 1 >= 0)

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    const long long NEG_INF = -(1LL << 60);

    vector<long long> dpL(M, NEG_INF), dpS(M, NEG_INF), dpR(M, NEG_INF);
    vector<long long> ndpL(M), ndpS(M), ndpR(M);

    for (int i = 0; i < N; i++) {
        vector<long long> G(M);
        for (int j = 0; j < M; j++) cin >> G[j];

        if (i == 0) {
            for (int j = 0; j < M; j++) {
                dpS[j] = G[j];
            }
            continue;
        }

        fill(ndpL.begin(), ndpL.end(), NEG_INF);
        fill(ndpS.begin(), ndpS.end(), NEG_INF);
        fill(ndpR.begin(), ndpR.end(), NEG_INF);

        for (int j = 0; j < M; j++) {
            ndpS[j] = max({dpL[j], dpS[j], dpR[j]}) + G[j];

            if (j + 1 < M) {
                ndpL[j] = max(dpS[j + 1], dpR[j + 1]) + G[j];
            }

            if (j - 1 >= 0) {
                ndpR[j] = max(dpS[j - 1], dpL[j - 1]) + G[j];
            }
        }

        dpL.swap(ndpL);
        dpS.swap(ndpS);
        dpR.swap(ndpR);
    }

    long long ans = NEG_INF;
    for (int j = 0; j < M; j++) {
        ans = max({ans, dpL[j], dpS[j], dpR[j]});
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.