| Submit | All submissions | Best solutions | Back to list |
EIUGAME - Maximum path sum |
Given a matrix of n rows and m columns numbered from top to bottom, left to right, each cell in the matrix is a random number whose absolute value does not exceed 10^9. From the upper left position, find a path to the lower right corner position so that the number of squares to go through is minimal (each move only goes to the square with a common edge). Among those ways, find a way to maximize the sum of the values of the cells on the path.
Input
The first line is 2 integers n, m (n, m<=2x10^3).
The ith line of the next n lines contains m space-separated integers. The jth value in line i corresponds to the aij value in the matrix(|a|<=10^9).
The first line is 2 integers n, m (n, m<=2x10^3).
The ith line of the next n lines contains m space-separated integers. The jth value in line i corresponds to the aij value in the matrix(|a|<=10^9).
Output
A single integer that is the maximum sum along the path found.
Example
Input:
3 3
1 2 3
-1 5 6
0 2 9
Output:
23
| Added by: | Ha Minh Ngoc |
| Date: | 2015-05-22 |
| Time limit: | 1s-3s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: MAWK BC NCSHARP COFFEE DART FORTH GOSU JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA |