Overview

This problem asks you to choose a course sliding down from top to bottom on an \(N \times M\) grid, maximizing the total score of cells you pass through, under the constraint that “you cannot turn in the same direction twice consecutively (zigzag constraint).” We solve it using dynamic programming (DP).

Analysis

Key Insight

The key point of this problem is how to handle the zigzag constraint that “prohibits consecutive movements in the same direction.”

For example, if you arrived at the current cell by “moving right (\(d=+1\)),” then on the next move you cannot go right (\(d=+1\)) again. However, you can go straight (\(d=0\)) or left (\(d=-1\)).

In other words, which directions you can move next depends on the previous movement direction. This is information that should be maintained as a “state.”

Problem with the Naive Approach

If you enumerate all possible courses, there are up to 3 choices at each row, resulting in \(O(3^N)\) possibilities, which is far too slow.

Solution

By adding the previous movement direction to the DP state, we can compute transitions in \(O(1)\) for each cell and state, solving the entire problem in \(O(NM)\).

Algorithm

State Definition

\(dp[r][c][s]\): The maximum total score when arriving at column \(c\) of row \(r\) with state \(s\)

State \(s\) has the following 3 types: - State 0: Arrived by going straight (\(d=0\)), or the starting position - State 1: Arrived by moving right (\(d=+1\)) - State 2: Arrived by moving left (\(d=-1\))

Transitions

Consider arriving at column \(c\) of row \(r\):

1. Arrived by going straight (\((r-1, c) \to (r, c)\)):
   Coming from the same column of the previous row. Any previous state is OK.
   \(\text{new\_dp0}[c] = \max(dp0[c], dp1[c], dp2[c]) + G[r][c]\)

2. Arrived by moving right (\((r-1, c-1) \to (r, c)\)):
   Coming from column \(c-1\) of the previous row. However, you cannot come from state 1 (previous move was also right).
   \(\text{new\_dp1}[c] = \max(dp0[c-1], dp2[c-1]) + G[r][c]\)

3. Arrived by moving left (\((r-1, c+1) \to (r, c)\)):
   Coming from column \(c+1\) of the previous row. However, you cannot come from state 2 (previous move was also left).
   \(\text{new\_dp2}[c] = \max(dp0[c+1], dp1[c+1]) + G[r][c]\)

Initial Values and Answer

• Initial values: For all columns \(c\) in row 1, \(dp0[c] = G[0][c]\) (starting position)
• Answer: The maximum value across all columns and all states in row \(N\)

Concrete Example

Consider a 3-row, 3-column grid with columns numbered 1, 2, 3 from the left. If you are at column 2 in row 1 and move to column 3 in row 2 (right move), then you are in state 1. In the next row 3: - Move to column 2 (left move) → OK ✓ - Move to column 3 (go straight) → OK ✓ - Move to column 4 (right move) → NG ✗ (two consecutive right moves)

Complexity

• Time complexity: \(O(NM)\) — Computing transitions for 3 states per cell in \(O(1)\)
• Space complexity: \(O(M)\) — Since we update the DP table row by row, we only keep information from the previous row

Implementation Notes

• By updating the DP array row by row (computing new row values by referencing previous row values), space is kept to \(O(M)\).

• Unreachable states are represented by NEG_INF = -10^18, and only reachable states are used in transitions.

• Since the input can be large (\(NM \leq 2 \times 10^6\)), we use sys.stdin.buffer.read() for fast input reading.

• In Python, due to high constant factors, this solution may be borderline (PyPy may be recommended in some cases).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    
    G = []
    for i in range(N):
        row = [int(data[idx + j]) for j in range(M)]
        idx += M
        G.append(row)
    
    NEG_INF = -10**18
    
    # state 0: arrived straight (or start), state 1: arrived via d=+1 (right), state 2: arrived via d=-1 (left)
    dp0 = [NEG_INF] * M
    dp1 = [NEG_INF] * M
    dp2 = [NEG_INF] * M
    
    for c in range(M):
        dp0[c] = G[0][c]
    
    for r in range(1, N):
        new_dp0 = [NEG_INF] * M
        new_dp1 = [NEG_INF] * M
        new_dp2 = [NEG_INF] * M
        gr = G[r]
        
        for c in range(M):
            # Arrive via straight (d=0): from (r-1, c), any previous state allowed
            v0 = dp0[c]
            v1 = dp1[c]
            v2 = dp2[c]
            val = v0
            if v1 > val: val = v1
            if v2 > val: val = v2
            if val != NEG_INF:
                new_dp0[c] = val + gr[c]
            
            # Arrive via right (d=+1): from (r-1, c-1), exclude state 1 (can't have two rights)
            if c > 0:
                v0 = dp0[c - 1]
                v2 = dp2[c - 1]
                val = v0
                if v2 > val: val = v2
                if val != NEG_INF:
                    new_dp1[c] = val + gr[c]
            
            # Arrive via left (d=-1): from (r-1, c+1), exclude state 2 (can't have two lefts)
            if c < M - 1:
                v0 = dp0[c + 1]
                v1 = dp1[c + 1]
                val = v0
                if v1 > val: val = v1
                if val != NEG_INF:
                    new_dp2[c] = val + gr[c]
        
        dp0 = new_dp0
        dp1 = new_dp1
        dp2 = new_dp2
    
    ans = NEG_INF
    for c in range(M):
        if dp0[c] > ans: ans = dp0[c]
        if dp1[c] > ans: ans = dp1[c]
        if dp2[c] > ans: ans = dp2[c]
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.