Maximum sum of 2 paths on a matrix
Difference between en1 and en2, changed 429 character(s)
You're given a matrix A$A$ of size $N * M$, consisting of integers satisfying $|A[i][j]| <= 100_{i,j}| \leqslant 100$. Rows are numbered $1$ to $N$ downward, and columns are numbers $1$ to $N$ from left to right. There are 2 players, each one will move from point block $(1, 1)$ to point block $(N, M)$ and can only move to the right or downward (A[1][1] = A[N][M] = 0). 2 paths made by the 2 players can only have $(1, 1)$ and $(N, M)$ as two common pointblocks. All other points in the 2 paths must be distinct. Find the 2 paths that have maximum sum.↵
↵
**Input:** the first line consists of 2 numbers are N and M.$N$ and $M$.↵
↵
Next N$N$ lines consist of M$M$ integers describing the matrix A$A$. Note that A[1][1] = A[N][M]$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**↵
↵
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English goldenskygiang 2019-04-08 17:12:09 3 Tiny change: 'are numbers $1$ to $N' -> 'are numbered $1$ to $N'
en5 English goldenskygiang 2019-04-08 07:17:59 23 Tiny change: '$ and $M$.\n\nNext $' -> '$ and $M$. $(N, M \leqslant 200)$\n\nNext $'
en4 English goldenskygiang 2019-04-07 19:24:44 14 Tiny change: 'aximum sum.\n\n**Inp' -> 'aximum sum when combined.\n\n**Inp'
en3 English goldenskygiang 2019-04-07 19:24:14 8 Tiny change: 'All other points in the 2' -> 'All other blocks in the 2'
en2 English goldenskygiang 2019-04-07 19:23:06 429 Tiny change: '|A_{i,j}| <= 100$. The' -> '|A_{i,j}| \leqslant 100$. The' (published)
en1 English goldenskygiang 2019-04-07 15:18:26 681 Initial revision (saved to drafts)