← 返回题目

题库练习 Maximum path

← 上一题下一题 →

A10856 | $Maximum path$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You are given a rectangular table $3\timesn$ . 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.

输入格式

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.

输出格式

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

输出 #1

输入 #2

5
10 10 10 -1 -1
-1 10 10 10 10
-1 10 10 10 10

输出 #2

C++ 编辑器

输入

输出