Maximum path 2 - MarisaOJ: Marisa Online Judge

Maximum path 2

Time limit: 1000 ms
Memory limit: 256 MB
The forest is a $n \times n$ board. From cell $(i, j)$, Marisa can go to $(i + 1, j)$ or $(i, j + 1)$. Cell $(i, j)$ has $A_{i, j}$ mushrooms. Marisa's journey start from $(1, 1)$ and end at $(n, n)$, what is the maximum number of mushrooms her can obtain? ### Input - n lines, each line contains n integers. ### Output - The maximum number of mushrooms Marisa can obtain. ### Constraints - $1 \le n \le 1000$. - $1 \le A_{i, j} \le 10^9$. ### Example Input: ``` 4 2 2 2 1 1 1 2 1 1 1 2 1 1 1 2 2 ``` Output: ``` 14 ```