Overview

On an \(N \times M\) grid, moving from the top-left to the bottom-right using only “right” or “down” moves, the problem asks to maximize the total value of gems on the cells you pass through.

Analysis

The key point of this problem is that “the state immediately before reaching a cell \((i, j)\) must be either ‘the cell above \((i-1, j)\)’ or ‘the cell to the left \((i, j-1)\)’”.

Why Dynamic Programming (DP)?

When we want to find the maximum total value up to a specific cell \((i, j)\), regardless of what the earlier path looked like, if we know the maximum total value obtainable up to \((i-1, j)\) or \((i, j-1)\), we can compute the maximum value at \((i, j)\). In this way, “Dynamic Programming (DP)” — a technique that breaks a large problem into smaller subproblems and reuses their results — is the optimal approach.

If we tried to naively examine all paths using recursion (such as depth-first search), the number of paths would be enormous (up to \({}_{N+M-2}C_{N-1}\) paths), and it would not finish within the time limit. By using DP, we only need to compute each cell once.

Algorithm

Definition of the DP

Define \(dp[i][j]\) as “the maximum total value of gems when reaching cell \((i, j)\).”

Transition Formula

There are two ways to arrive at cell \((i, j)\): “from above” or “from the left.” Therefore, we can update using the following formula: - \(dp[i][j] = A_{i,j} + \max(dp[i-1][j], dp[i][j-1])\)

However, there are exceptions for edge cells: - Starting cell: \(dp[1][1] = A_{1,1}\) - First row: You can only come from the left, so \(dp[1][j] = dp[1][j-1] + A_{1,j}\) - First column: You can only come from above, so \(dp[i][1] = dp[i-1][1] + A_{i,1}\)

Space Complexity Optimization

Normally, the DP table is managed as a 2D array of size \(N \times M\), but computing the current row only requires information from “the row above” and “the cell to the left in the current row.” Therefore, by reusing a 1D array (of size \(M\)) and updating it in place, we can save memory usage.

Complexity

• Time complexity: \(O(N \times M)\)
  • Since we scan all cells in the grid (\(N \times M\) cells) exactly once, the complexity is proportional to the number of cells.
• Space complexity: \(O(M)\)
  • When managing the DP with a 1D array, only memory for \(M\) columns is used.

Implementation Notes

• Fast input processing: Since \(N, M\) can be up to 1000 and the number of elements can reach \(10^6\), in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar.

• 1D DP updates:

  • When updating dp[j], the pre-update dp[j] represents “the value of the cell above,” and the already-updated dp[j-1] represents “the value of the cell to the left.” Using this, we can concisely write dp[j] = val + max(dp[j], dp[j-1]).

• Initialization: Since the first row can only be computed by “accumulating from the left,” handling it separately outside the loop makes the main loop for the second row onward simpler.

  Source Code

import sys

def solve():
    # 入力をすべて読み込み、空白で分割して整数のイテレータを作成
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    it = map(int, input_data)
    
    # グリッドのサイズを取得
    try:
        N = next(it)
        M = next(it)
    except StopIteration:
        return
    
    # dp[j] は現在の行の j 列目に到達したときの宝石の価値の最大合計値を保持する
    dp = [0] * M
    
    # 1行目の初期化（右方向にのみ移動可能）
    current_sum = 0
    for j in range(M):
        current_sum += next(it)
        dp[j] = current_sum
        
    # 2行目以降の更新
    for _ in range(1, N):
        # 各行の最初の列（上からのみ移動可能）
        dp[0] += next(it)
        # その他の列（上または左から移動可能）
        for j in range(1, M):
            val = next(it)
            # dp[j-1] は左のマス(i, j-1)からの最大値、dp[j] は上のマス(i-1, j)からの最大値
            if dp[j-1] > dp[j]:
                dp[j] = dp[j-1] + val
            else:
                dp[j] = dp[j] + val
                
    # 右下のマス (N, M) に到達したときの最大値を出力
    print(dp[M-1])

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.