Overview

Since you can only move right or down, we compute the “maximum obtainable value” for each cell in order using dynamic programming (DP), and output the value at the bottom-right cell \((N,M)\) as the answer.

Analysis

This problem asks “which path maximizes the total value?” However, there are \(\binom{N+M-2}{N-1}\) possible paths in total, and for \(N,M \le 1000\), enumerating all of them is impossible (it grows exponentially, resulting in TLE).

The key observation is as follows:

• The cell visited immediately before reaching cell \((i,j)\), given the movement constraints (right and down only), can only be:
  • Above: coming down from \((i-1,j)\)
  • Left: coming right from \((i,j-1)\)

There are only 2 possibilities. - Therefore, the “maximum value up to \((i,j)\)” can be computed by taking the larger of the maximum values up to those two cells, and adding the gem value \(A_{i,j}\) of the current cell.

For example, in a \(3 \times 3\) grid, to reach \((2,3)\) you can only come from \((1,3)\) or \((2,2)\), so the “maximum up to \((2,3)\)” is determined by taking the maximum of “maximum up to \((1,3)\)” and “maximum up to \((2,2)\)”.

Since we can decompose the “large problem (reaching the goal)” into “smaller problems (reaching each cell)” like this, DP is applicable.

Algorithm

1. DP Definition (2-dimensional formulation)

\(dp[i][j] =\) the maximum total gem value obtainable when reaching cell \((i,j)\) (\(1\)-indexed)

The transition is as follows:

• \(dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1]) + A_{i,j}\)

(Take the maximum of coming from above or coming from the left)

2. Compression to 1 Dimension (Memory Reduction)

Since \(N,M \le 1000\), storing \(dp\) as an \(N \times M\) array would fit in time, but more cleverly we can keep only one row.

In the code: - dp[j] is used as “the maximum value at column \(j\) in the currently processed row.” - When processing rows from top to bottom, the pre-update dp[j] represents “the value from above (previous row),” and the already-updated dp[j-1] represents “the value from the left (one column back in the same row).”

Update formula (inside the code): - up = dp[j] (before update, so it represents above) - left = dp[j-1] (after update, so it represents left) - dp[j] = max(left, up) + a

Boundary handling (leftmost column): - At column \(1\) (i.e., j==0 in the code), there is no left neighbor, so left is set to a very small value NEG to prevent “coming from the left” from being selected.

Finally, dp[M-1] is the answer for \((N,M)\).

Complexity

• Time complexity: \(O(NM)\) (each cell is processed exactly once)
• Space complexity: \(O(M)\) (the DP array only stores one row’s width)

Implementation Notes

• The update order of the 1-dimensional DP is important. We rely on the relationship that dp[j-1] on the left is already updated for the current row, while dp[j] from above is not yet updated.

• Since the input can have up to \(10^6\) elements, we use sys.stdin.buffer.readline for fast reading.

• For boundary handling, at the leftmost column (j==0), left is set to NEG to prevent invalid transitions.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    dp = [0] * M
    NEG = -10**30

    for _ in range(N):
        row = list(map(int, input().split()))
        for j, a in enumerate(row):
            left = dp[j - 1] if j > 0 else NEG
            up = dp[j]
            dp[j] = (left if left > up else up) + a

    print(dp[M - 1])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.