#F. 阿Q的环状矩阵

    Type: Default 1000ms 256MiB

阿Q的环状矩阵

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

阿Q有一个神奇的矩阵,这个矩阵是环状的,它的第一行与最后一行相连,第一列与最后一列相连,即第一行的上一行为最后一行,最后一行的下一行为第一行,第一列的左一列为最后一列,最后一列的右一列为第一列。他想知道这个矩阵的最大非空子矩阵和是多大,非空子矩阵指不为空且由相连的若干列和若干行组成的矩阵,原矩阵每个位置最多出现一次。

输入格式

第一行输入两个整数 n,m 代表矩阵的长和宽。(1n,m90)(1 \leq n,m \leq 90) 接下来 n 行,每行 m 个整数,ai1,ai2,ai3aima_{i1},a_{i2},a_{i3}\cdots a_{im},代表第 i 行的 m 个数。(109aij109)(-10^9 \leq a_{ij} \le 10^9) 输出格式 输出一个整数,代表这个环形矩阵的最大非空子矩阵和。

样例输入

3 3
1 -2 3
-4 5 -6
7 -8 9

样例输出

20

字段和子序列 -- 动态规划

Not Claimed
Status
Done
Problem
8
Open Since
2024-12-13 0:00
Deadline
2024-12-20 23:59
Extension
24 hour(s)