A10856. Maximum path
编程题
普及/提高-
知识点
题目描述
You are given a rectangular table $3×n$ . Each cell contains an integer. You can move from one cell to another if they share a side.
Find such path from the upper left cell to the bottom right cell of the table that doesn't visit any of the cells twice, and the sum of numbers written in the cells of this path is maximum possible.
Find such path from the upper left cell to the bottom right cell of the table that doesn't visit any of the cells twice, and the sum of numbers written in the cells of this path is maximum possible.
输入格式
The first line contains an integer $n$ ( $1<=n<=10^{5}$ ) — the number of columns in the table.
Next three lines contain $n$ integers each — the description of the table. The $j$ -th number in the $i$ -th line corresponds to the cell $a_{ij}$ ( $-10^{9}<=a_{ij}<=10^{9}$ ) of the table.
Next three lines contain $n$ integers each — the description of the table. The $j$ -th number in the $i$ -th line corresponds to the cell $a_{ij}$ ( $-10^{9}<=a_{ij}<=10^{9}$ ) of the table.
输出格式
Output the maximum sum of numbers on a path from the upper left cell to the bottom right cell of the table, that doesn't visit any of the cells twice.
输入输出样例
输入 #1
3 1 1 1 1 -1 1 1 1 1
输出 #1
7
输入 #2
5 10 10 10 -1 -1 -1 10 10 10 10 -1 10 10 10 10
输出 #2
110
说明/提示
The path for the first example:
The path for the second example:
The path for the second example:
