Overview

This problem asks for the maximum score obtainable when skiing down a grid-shaped ski slope according to specific rules. Since movement has the constraint that “you cannot move diagonally in the same direction consecutively (zigzag condition),” we efficiently find the solution using Dynamic Programming (DP) while maintaining the previous movement direction as part of the state.

Analysis

1. Naive Approach and Its Limitations

From each cell \((r, c)\), there are at most \(3\) ways to move to the next row: “lower-left,” “directly below,” and “lower-right.” If we perform an exhaustive search such as depth-first search (DFS) exploring all paths, the number of paths becomes \(O(3^N)\), which will not finish within the time limit for \(N \le 2000\).

2. Understanding the Zigzag Condition

The key to this problem is the “prohibition of consecutive moves in the same diagonal direction.” Let \(d\) denote the change in column: - After a lower-left move (\(d = -1\)), you cannot move lower-left (\(d = -1\)). You must move directly below (\(d = 0\)) or lower-right (\(d = 1\)). - After a lower-right move (\(d = 1\)), you cannot move lower-right (\(d = 1\)). You must move directly below (\(d = 0\)) or lower-left (\(d = -1\)). - After a directly below move (\(d = 0\)), you can move in any direction (\(d \in \{-1, 0, 1\}\)).

Thus, the available directions for the next move depend on “which direction you came from immediately before.” Therefore, to compute the maximum score upon reaching each cell, we need to maintain not just “which cell we are at” but also “from which direction we arrived at that cell” as part of the state.

Algorithm

Dynamic Programming (DP) Definition

For each row \(r\), we maintain the state at column \(c\) split into the following \(3\) categories:

• \(dp_0[c]\): Maximum score when arriving at cell \((r, c)\) with the previous move being directly below (\(d = 0\))
• \(dp_1[c]\): Maximum score when arriving at cell \((r, c)\) with the previous move being lower-left (\(d = -1\))
• \(dp_2[c]\): Maximum score when arriving at cell \((r, c)\) with the previous move being lower-right (\(d = 1\))

State Transitions

The transition from the DP table of row \(r-1\) to the new DP table (next_dp) of row \(r\) is as follows (let the score of the cell be \(G[r][c]\)):

1. Move directly below (\(next\_dp_0[c]\))

   • There is no restriction on the previous move. We can transition from any state at the same column \(c\) in row \(r-1\). $\(next\_dp_0[c] = \max(dp_0[c], dp_1[c], dp_2[c]) + G[r][c]\)$

2. Move lower-left (\(next\_dp_1[c]\))

   • This is a transition from column \(c+1\) in row \(r-1\).
   • The previous move must not be “lower-left (\(dp_1\)),” so the source is limited to \(dp_0\) or \(dp_2\). $\(next\_dp_1[c] = \max(dp_0[c+1], dp_2[c+1]) + G[r][c]\)\( *(Note: When \)c = M-1\( (rightmost), there is no transition from further right, so we set it to \)-\infty$)*

3. Move lower-right (\(next\_dp_2[c]\))

   • This is a transition from column \(c-1\) in row \(r-1\).
   • The previous move must not be “lower-right (\(dp_2\)),” so the source is limited to \(dp_0\) or \(dp_1\). $\(next\_dp_2[c] = \max(dp_0[c-1], dp_1[c-1]) + G[r][c]\)\( *(Note: When \)c = 0\( (leftmost), there is no transition from further left, so we set it to \)-\infty$)*

Initial Values

Since we start from the first row (\(r = 0\)), the initial cells are treated as “no previous move (equivalent to a directly below move).” - \(dp_0[c] = G[0][c]\) - \(dp_1[c] = -\infty\) - \(dp_2[c] = -\infty\)

After repeating the transitions up to row \(N\), the answer is the maximum value across all states: \(\max(dp_0, dp_1, dp_2)\).

Complexity

• Time Complexity: \(O(N \times M)\) For each row update, transitions for \(M\) columns are performed in constant time \(O(1)\). Repeating this \(N\) times gives an overall complexity of \(O(N \times M)\), which runs sufficiently fast for the constraint \(N \times M \le 2 \times 10^6\).

• Space Complexity: \(O(N \times M)\) \(O(N \times M)\) memory is used to store the grid information. Since only the previous row’s DP table needs to be retained, the memory required for the DP itself is only \(O(M)\).

Implementation Notes

• Optimization in Python (Using slices and zip) Naively running nested loops in Python may cause issues with the time limit (TL). In the presented code, slices and zip are used to compute each column in bulk (in a vectorized manner) for faster execution:

  # next_dp1[c] transitions from column c+1, so we slice with [1:] and compute max values in bulk
  next_dp1 = [max(a, b) + x for a, b, x in zip(dp0[1:], dp2[1:], g[:-1])] + [-INF]
  

  This dramatically reduces loop overhead and achieves fast execution.

• Setting infinity (INF) A sufficiently small value (-INF) is used to exclude impossible paths (such as transitions from outside the grid). In this problem, since the maximum total score can reach \(N \times \max(G_{i,j}) = 2000 \times 10^9 = 2 \times 10^{12}\), INF is set to 10**18, which is sufficiently large.

  Source Code

import sys


def solve():
    # Read all inputs from standard input
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])

    # Flattened grid values converted to integers
    flat_G = list(map(int, input_data[2:]))

    # Reconstruct 2D grid
    G = []
    for r in range(N):
        G.append(flat_G[r * M : (r + 1) * M])

    INF = 10**18

    # dp0[c]: Max score at (r, c) where the last move was straight down (d = 0)
    # dp1[c]: Max score at (r, c) where the last move was down-left (d = -1)
    # dp2[c]: Max score at (r, c) where the last move was down-right (d = 1)
    dp0 = G[0][:]
    dp1 = [-INF] * M
    dp2 = [-INF] * M

    for r in range(1, N):
        g = G[r]

        # Transition for state 0 (straight down): can come from any state 0, 1, 2
        next_dp0 = [max(a, b, c) + x for a, b, c, x in zip(dp0, dp1, dp2, g)]

        # Transition for state 1 (down-left): must come from state 0 or 2 (not 1)
        # next_dp1[c] comes from column c+1
        next_dp1 = [
            max(a, b) + x for a, b, x in zip(dp0[1:], dp2[1:], g[:-1])
        ] + [-INF]

        # Transition for state 2 (down-right): must come from state 0 or 1 (not 2)
        # next_dp2[c] comes from column c-1
        next_dp2 = [-INF] + [
            max(a, b) + x for a, b, x in zip(dp0[:-1], dp1[:-1], g[1:])
        ]

        dp0 = next_dp0
        dp1 = next_dp1
        dp2 = next_dp2

    # The answer is the maximum value in any state at the last row
    ans = max(max(dp0), max(dp1), max(dp2))
    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.