Overview

This problem asks you to maximize the total score of cells visited while moving from top to bottom one row at a time.
However, you cannot move in the same horizontal direction twice consecutively, such as “right→right” or “left→left”.

Analysis

From each row, the possible destinations in the next row are:

• Lower-left
• Directly below
• Lower-right

giving 3 options.

If we naively try all paths, each row branches into up to 3 choices, resulting in approximately \(3^{N-1}\) paths, which is far too many.

So we consider dynamic programming.

In a standard “top-to-bottom grid DP”, we only need to maintain:

“the maximum score to reach the current cell”

However, this problem has a zigzag constraint.
For example, if the previous move was to the right, the next move cannot also be to the right.

In other words, whether the next move is allowed depends on “the previous horizontal direction of movement.”
Therefore, we maintain the following 3 states for each cell:

• The last move was straight down
• The last move was to the right
• The last move was to the left

Here, if we denote the change in column index as \(d\):

• Straight down: \(d = 0\)
• Right move: \(d = +1\)
• Left move: \(d = -1\)

A straight-down move does not affect the zigzag constraint, so it can be performed after any direction.
On the other hand, a right move is forbidden if the previous move was also to the right, and a left move is forbidden if the previous move was also to the left.

Algorithm

We prepare the following 3 DP arrays:

• z[j]: Maximum score when at column \(j\) of the current row, with the last move being straight down
• p[j]: Maximum score when at column \(j\) of the current row, with the last move being to the right
• m[j]: Maximum score when at column \(j\) of the current row, with the last move being to the left

Column indices are 0-based in the implementation.

Initialization

In the first row, no movement has been made yet.
In this code, we treat it as “the last move was straight down”:

z = first
p = [NEG] * M
m = [NEG] * M

NEG is a sufficiently small value representing an unreachable state.

Transitions

Let row[j] be the value at column \(j\) of the next row.

Moving straight down

We come from the same column \(j\) of the previous row.
A straight-down move is allowed regardless of the previous direction, so:

\[ nz[j] = \max(z[j], p[j], m[j]) + row[j] \]

Moving to the right

We come from column \(j-1\) of the previous row to the current column \(j\).
This is a move where the column increases by \(+1\).

However, if the previous move was also to the right, it is forbidden, so only z[j-1] or m[j-1] can be used:

\[ np[j] = \max(z[j-1], m[j-1]) + row[j] \]

This is only possible when \(j > 0\).

Moving to the left

We come from column \(j+1\) of the previous row to the current column \(j\).
This is a move where the column decreases by \(-1\).

If the previous move was also to the left, it is forbidden, so only z[j+1] or p[j+1] can be used:

\[ nm[j] = \max(z[j+1], p[j+1]) + row[j] \]

This is only possible when \(j+1 < M\).

Answer

Since we can end at any column in the last row, and the last direction of movement does not matter:

\[ \max(\max(z), \max(p), \max(m)) \]

is the answer.

Complexity

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

We only perform a constant number of transitions per cell.
Also, since the DP only requires the previous row, we can process one row at a time without storing the entire grid.

Implementation Notes

To represent unreachable states, we use a sufficiently small value NEG = -10**30.

The maximum possible total score is at most:

\[ N \times 10^9 \]

so under the constraint \(N \leq 2000\), -10**30 is sufficiently small.

Also, when \(N=1\), there are no moves, so the maximum value in the first row is directly the answer.
In this implementation, this is naturally handled by taking the answer from the initial state z = first as-is.

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())

    first = list(map(int, input().split()))
    NEG = -10**30

    z = first
    p = [NEG] * M
    m = [NEG] * M

    for _ in range(1, N):
        row = list(map(int, input().split()))

        nz = [NEG] * M
        np = [NEG] * M
        nm = [NEG] * M

        zz = z
        pp = p
        mm = m
        rr = row

        for j in range(M):
            g = rr[j]

            a = zz[j]
            b = pp[j]
            c = mm[j]
            if b > a:
                a = b
            if c > a:
                a = c
            nz[j] = a + g

            if j > 0:
                a = zz[j - 1]
                b = mm[j - 1]
                if b > a:
                    a = b
                np[j] = a + g

            if j + 1 < M:
                a = zz[j + 1]
                b = pp[j + 1]
                if b > a:
                    a = b
                nm[j] = a + g

        z, p, m = nz, np, nm

    ans = max(max(z), max(p), max(m))
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.