#B4335. [中山市赛 2023] 互质
[中山市赛 2023] 互质
题目描述
给定一个整数 与 的矩阵 ,在 中放置若干个不重叠的 子矩阵,使它们覆盖的元素和最大,求它们覆盖的元素和。
若没有放置任何子矩阵,则答案为 。
输入格式
第一行一个整数 。
接下来 行每行 个整数,第 行第 个整数表示 。
输出格式
一行一个整数,表示答案。
5
1 2 3 4 5
5 4 3 2 1
1 2 -9 4 5
1 2 3 4 5
5 4 3 2 1
18
10
98 78 -97 -36 94 44 42 69 50 7
54 -54 -36 -56 98 69 59 36 52 80
90 36 65 -23 -33 65 12 79 -38 0
81 -19 65 73 32 -57 -79 -66 89 6
92 63 1 61 -96 -41 25 -44 -53 25
55 83 78 -41 -34 16 62 87 79 62
-63 91 -30 -33 91 39 92 92 29 92
74 39 44 25 29 50 -63 65 77 75
-26 -78 -92 55 -45 45 74 53 62 58
3 92 -4 -76 -60 -24 90 72 53 95
2921
提示
样例解释 1
矩阵中仅能放置一个 的子矩阵,令其左上角为 ,此时其覆盖的元素为 ,和为 。
样例解释 2
一种解的各子矩阵左上角为 。
数据范围
对于 的数据,。
对于另外 的数据, 中仅包含正整数。
对于 的数据,,对于任意 满足 。