Overview

This is a dynamic programming problem where you slide down an \(N \times M\) grid from top to bottom, maximizing the total score of cells you pass through, under a zigzag constraint that “you cannot move in the same direction (left-left or right-right) two consecutive times.”

Analysis

Key Insight

You cannot correctly determine whether the zigzag constraint is satisfied by recording only the position at each row — you must also record which direction you moved in the previous step.

For example, regarding the column change \(d_r = c_{r+1} - c_r\): - \(d_r > 0\) (move right) followed by \(d_{r+1} > 0\) (move right) is forbidden - \(d_r < 0\) (move left) followed by \(d_{r+1} < 0\) (move left) is forbidden - \(d_r = 0\) (go straight) can be followed by movement in any direction

Problem with the Naive Approach

If we simply define dp[r][c] = “maximum score when reaching column \(c\) at row \(r\)”, we cannot account for the zigzag constraint when transitioning to the next row, because the previous movement direction is unknown.

Solution

We add the previous movement direction to the DP state. Since there are 3 possible directions — “left (\(d < 0\))”, “straight (\(d = 0\))”, and “right (\(d > 0\))” — the number of states becomes \(O(N \times M \times 3)\), which fits within the constraints.

Algorithm

We define the DP states as follows:

• \(\text{dp}[c][0]\): maximum score when reaching column \(c\) of the current row via a left move (column decreases)
• \(\text{dp}[c][1]\): maximum score when reaching column \(c\) of the current row via going straight (column unchanged)
• \(\text{dp}[c][2]\): maximum score when reaching column \(c\) of the current row via a right move (column increases)

Transitions

Consider reaching column \(c\) of the next row:

1. Arriving via left move (coming from column \(c+1\) of the previous row):
   The previous movement direction must be straight (1) or right (2) (left→left is forbidden)
   \(\text{ndp}[c][0] = \max(\text{dp}[c+1][1],\ \text{dp}[c+1][2]) + G[r][c]\)

2. Arriving via going straight (coming from column \(c\) of the previous row):
   The previous movement direction can be anything
   \(\text{ndp}[c][1] = \max(\text{dp}[c][0],\ \text{dp}[c][1],\ \text{dp}[c][2]) + G[r][c]\)

3. Arriving via right move (coming from column \(c-1\) of the previous row):
   The previous movement direction must be left (0) or straight (1) (right→right is forbidden)
   \(\text{ndp}[c][2] = \max(\text{dp}[c-1][0],\ \text{dp}[c-1][1]) + G[r][c]\)

Initialization

At row 1, no movement has occurred yet, so for all columns \(c\), we set \(\text{dp}[c][1] = G[1][c]\) (treated as going straight, allowing transition in any direction afterward).

Answer

Take the maximum value across all columns and all directions in the final row.

Complexity

• Time complexity: \(O(N \times M)\) (constant number of operations per cell)
• Space complexity: \(O(M)\) (only maintaining DP arrays for the current row and the next row)

Implementation Notes

• By initializing the initial state as “straight (direction 1)”, we naturally allow transitions in any direction from row 1.

• We use NEG_INF = -10^{18} to distinguish unreachable states. A val != NEG_INF check is included to prevent transitions from unreachable states.

• We save memory by reusing DP arrays with swap(dp, ndp).

• When \(N = 1\), no movement occurs, so we handle this as a special case by directly outputting the maximum value in row 1.

  Source Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    const long long NEG_INF = -1e18;
    vector<array<long long, 3>> dp(M, {NEG_INF, NEG_INF, NEG_INF});
    vector<array<long long, 3>> ndp(M, {NEG_INF, NEG_INF, NEG_INF});
    
    // Read and process row 0
    for (int c = 0; c < M; c++) {
        long long g;
        cin >> g;
        dp[c][1] = g;
    }
    
    if (N == 1) {
        long long ans = NEG_INF;
        for (int c = 0; c < M; c++) ans = max(ans, dp[c][1]);
        cout << ans << endl;
        return 0;
    }
    
    // Process rows 1 to N-1
    for (int r = 1; r < N; r++) {
        vector<long long> row(M);
        for (int c = 0; c < M; c++) cin >> row[c];
        
        for (int c = 0; c < M; c++) {
            ndp[c] = {NEG_INF, NEG_INF, NEG_INF};
            
            // ndp[c][0]: arrived by moving left (from c+1 in previous row)
            // allowed after straight(1) or right(2)
            if (c + 1 < M) {
                long long val = max(dp[c+1][1], dp[c+1][2]);
                if (val != NEG_INF)
                    ndp[c][0] = val + row[c];
            }
            
            // ndp[c][1]: arrived by moving straight (from c in previous row)
            // allowed after any direction
            {
                long long val = max({dp[c][0], dp[c][1], dp[c][2]});
                if (val != NEG_INF)
                    ndp[c][1] = val + row[c];
            }
            
            // ndp[c][2]: arrived by moving right (from c-1 in previous row)
            // allowed after left(0) or straight(1)
            if (c - 1 >= 0) {
                long long val = max(dp[c-1][0], dp[c-1][1]);
                if (val != NEG_INF)
                    ndp[c][2] = val + row[c];
            }
        }
        
        swap(dp, ndp);
    }
    
    long long ans = NEG_INF;
    for (int c = 0; c < M; c++) {
        ans = max(ans, max({dp[c][0], dp[c][1], dp[c][2]}));
    }
    
    cout << ans << endl;
    return 0;
}

---

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