Overview

This problem asks you to maximize the total score when skiing down a grid-shaped ski slope from top to bottom under a “zigzag” movement restriction. Since there are restrictions on the direction of consecutive moves, this can be solved using Dynamic Programming (DP) while maintaining not only the current position but also the state of “which direction the previous move came from.”

Analysis

1. Organizing the “Zigzag” Conditions

When moving from the summit (row 1) to the base (row \(N\)), there are three possible movement directions to the next row below: - Lower-left (L): move where the column decreases by \(1\) - Directly below (D): move where the column stays the same - Lower-right ®: move where the column increases by \(1\)

The “zigzag” condition stated in the problem prohibits “two consecutive lower-left moves” and “two consecutive lower-right moves”. On the other hand, there are no restrictions on moves directly below (D) regardless of what moves come before or after.

Therefore, when moving to a cell \((r, c)\), the available next moves depend on what the previous move was: - If the previous move was lower-left (L) \(\to\) cannot move lower-left (L) next (only directly below or lower-right). - If the previous move was lower-right ® \(\to\) cannot move lower-right ® next (only lower-left or directly below). - If the previous move was directly below (D) \(\to\) can move in any direction next.

2. Why Doesn’t a Simple Search Work?

If you try to exhaustively search all paths (e.g., using depth-first search), the number of paths grows exponentially, and you won’t meet the time limit (TLE). However, when you reach a cell \((r, c)\), the optimal way to proceed from that point is determined solely by “which cell you are currently at” and “which direction you moved from previously.” The details of the path before that are irrelevant. Since the next transition is determined only by the current state without depending on the specific past path (Markov property), Dynamic Programming (DP) is effective.

---

Algorithm

DP Table Definition

Define the DP table as follows:

• \(dp[c][dir] :=\) the maximum score when arriving at column \(c\) of the current row via movement direction \(dir\)

Here, the previous movement direction \(dir\) is assigned as follows: - \(dir = 0\) (L): move from upper-right \((c+1)\) (lower-left move) - \(dir = 1\) (D): move from directly above \((c)\) (directly below move) - \(dir = 2\) ®: move from upper-left \((c-1)\) (lower-right move)

State Transitions

We transition row by row downward. Let \(dp\) be the DP table for the current row and \(next\_dp\) be the DP table for the next row. For each column \(c\) of the next row, we perform transitions for each of the 3 movement directions as follows:

1. Lower-left move (\(dir = 0\)) Moving from upper-right \((c+1)\). Due to the zigzag condition, the previous move must be something other than L (i.e., D or R). $\(next\_dp[c][0] = \max(dp[c+1][1], dp[c+1][2]) + G[r][c]\)\( *(Transition is only possible when \)c+1 < M$)*

2. Directly below move (\(dir = 1\)) Moving from directly above \((c)\). There are no restrictions on the previous move. $\(next\_dp[c][1] = \max(dp[c][0], dp[c][1], dp[c][2]) + G[r][c]\)$

3. Lower-right move (\(dir = 2\)) Moving from upper-left \((c-1)\). Due to the zigzag condition, the previous move must be something other than R (i.e., L or D). $\(next\_dp[c][2] = \max(dp[c-1][0], dp[c-1][1]) + G[r][c]\)\( *(Transition is only possible when \)c-1 \geq 0$)*

Initialization and Answer

• Initialization (row 1): Since you can start from any position in row 1, for any column \(c\), the score is \(G[0][c]\) regardless of the previous movement direction. \(dp[c][0] = dp[c][1] = dp[c][2] = G[0][c]\)
• Answer: After completing transitions up to row \(N\), the answer is the maximum value among \(dp[c][dir]\) over all columns \(c\) and all directions \(dir\).

---

Complexity

Time Complexity: \(O(N \times M)\)

Let \(N\) be the number of rows and \(M\) be the number of columns in the grid. For each row \(r\) (from \(1\) to \(N-1\)), we update 3 states for each column \(c\) (from \(0\) to \(M-1\)). Since the transition per cell takes constant time \(O(1)\), the overall complexity is \(O(N \times M)\). Given the constraint \(N \times M \le 2 \times 10^6\), this complexity is sufficiently fast and easily fits within the time limit.

Space Complexity: \(O(N \times M)\)

\(O(N \times M)\) memory is used to store the grid scores. For the DP table, since computing the next row only requires data from the immediately previous row, by preparing two arrays of size \(M \times 3\) (\(dp\) and \(next\_dp\)) and reusing them, the space complexity for DP can be reduced to \(O(M)\). Therefore, the overall space complexity is \(O(N \times M)\).

---

Implementation Notes

• Preventing Overflow: The maximum score per cell is \(10^9\), and you can ski down at most \(N = 2000\) rows, so the total score can reach \(2000 \times 10^9 = 2 \times 10^{12}\). This exceeds the maximum value of a 32-bit integer type (C++ int, approximately \(2 \times 10^9\)), so you must use a 64-bit integer type (C++ long long).

• Memory Savings and Speedup: In C++, when assigning the next row’s DP table to the current DP table, using dp = move(next_dp); allows you to switch arrays quickly by avoiding memory reallocation and copy overhead.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

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

    // dp[c][dir]
    // dir: 0 = L (直前の移動が左下、すなわち右上 c+1 からの移動)
    //      1 = D (直前の移動が真下、すなわち真上 c からの移動)
    //      2 = R (直前の移動が右下、すなわち左上 c-1 からの移動)
    vector<vector<long long>> dp(M, vector<long long>(3, -1));
    for (int c = 0; c < M; ++c) {
        dp[c][0] = G[0][c];
        dp[c][1] = G[0][c];
        dp[c][2] = G[0][c];
    }

    for (int r = 1; r < N; ++r) {
        vector<vector<long long>> next_dp(M, vector<long long>(3, -1));
        for (int c = 0; c < M; ++c) {
            // L: 右上 (c + 1) からの移動。直前が L 以外（D または R）である必要がある。
            if (c + 1 < M) {
                long long val = max(dp[c + 1][1], dp[c + 1][2]);
                if (val != -1) {
                    next_dp[c][0] = val + G[r][c];
                }
            }
            // D: 真上 (c) からの移動。直前の移動に制限はない。
            {
                long long val = max({dp[c][0], dp[c][1], dp[c][2]});
                if (val != -1) {
                    next_dp[c][1] = val + G[r][c];
                }
            }
            // R: 左上 (c - 1) からの移動。直前が R 以外（L または D）である必要がある。
            if (c - 1 >= 0) {
                long long val = max(dp[c - 1][0], dp[c - 1][1]);
                if (val != -1) {
                    next_dp[c][2] = val + G[r][c];
                }
            }
        }
        dp = move(next_dp);
    }

    long long ans = -1;
    for (int c = 0; c < M; ++c) {
        for (int d = 0; d < 3; ++d) {
            ans = max(ans, dp[c][d]);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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