### goldenskygiang's blog

By goldenskygiang, history, 9 months ago, ,

You're given a matrix $A$ of size $N * M$, consisting of integers satisfying $|A_{i,j}| \leqslant 100$. Rows are numbered $1$ to $N$ downward, and columns are numbered $1$ to $N$ from left to right. There are 2 players, each one will move from block $(1, 1)$ to block $(N, M)$ and can only move to the right or downward. 2 paths made by the 2 players can only have $(1, 1)$ and $(N, M)$ as two common blocks. All other blocks in the 2 paths must be distinct. Find the 2 paths that have maximum sum when combined.

Input: the first line consists of 2 numbers $N$ and $M$. $(N, M \leqslant 200)$

Next $N$ lines consist of $M$ integers describing the matrix $A$. Note that $A_{1,1} = A_{N,M} = 0$.

Output: The maximum sum of the 2 paths.

Example Input:

3 3

0 2 3

4 5 6

7 8 0

Example Output:

32

This problem was included in an offline contest that I participated yesterday. Other contestants said that this is a DP problem but I couldn't figure out the solution.