Treasure Hunt
Time limit2sMemory limit128 MB
Given a grid where the player travels down-right, then up-left, then down-right again, find the maximum treasure collected counting each cell only once per visit.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Matrix, Greedy
- Solved
- No attempts yet
Problem
Sejun is playing a new game where each level asks him to move through a map and collect treasure. The map has N rows and M columns, and each cell contains a number: the amount of treasure in that cell. The top-left cell always contains 0 treasure.
Sejun starts in the top-left cell and completes the following three stages in order.
- In the first stage, he may move only down or right, and he must finish at the bottom-right cell.
- In the second stage, he must return to the top-left cell, moving only up or left.
- In the third stage, he again may move only down or right, and he must finish at the bottom-right cell.
When Sejun visits a cell for the first time, he collects all treasure in that cell. If he visits the same cell again later, he collects nothing from it. Find the maximum total amount of treasure he can collect across the three stages.
Input
The first line contains two integers N and M, the number of rows and columns of the map. Each of the next N lines contains M integers, where each integer is the amount of treasure in that cell.
N and M are positive integers not greater than 50. Each cell value is a nonnegative integer not greater than 1,000.
Output
Print the maximum total amount of treasure that can be collected. The answer is less than or equal to 2147483647.