题目描述
小 E 同学非常喜欢书法,他听说 NOI2013 已经开始了,想题一幅 “NOI” 的字送给大家。
小 E 有一张非常神奇的纸,纸可以用一个 n 行 m 列的二维方格矩阵来表示,为了描述方便,我们定义矩阵左下角方格坐标为 (1,1),右上角方格坐标为 (m,n)。
矩阵的每个方格有一个整数的幸运值。在格子上面写字可以增加大家的幸运度,幸运度的大小恰好是所有被笔写到的方格的幸运值之和。现在你要在上面写
上 N
,O
,I
三个字母。
下面给出 3 个书法字的定义:
N
由若干(≥3)个边平行于坐标轴的矩形组成,设由 K 个矩形组成(标号 1…K),第 i 个矩形的左下角方格坐标设为 (Li,Bi),右上角坐标设为 (Ri,Ti),要求满足:
- Li≤Ri,Bi≤Ti;
- 对任意 1<i≤K,有 Li=Ri−1+1;
- 对任意 3≤i<K,有 Bi−1−1≤Ti≤Ti−1,Bi≤Bi−1;
- B2>B1,T2=T1,BK−1=BK,TK−1<TK;
O
由一个大矩形 A,挖去一个小矩形 B 得到,这两个矩形的边都平行于坐标轴。设大矩形 A 左下角的方格坐标为 (u,v),长为 W,宽为 H,则小矩形 B 满足左下角方格坐标为 (u+1,v+1),长 W−2,宽 H−2。要求满足:
- W≥3,H≥3;
- u>RK+1;
I
为 3 个边平行于坐标轴的从下到上的实心矩形组成,从下到上依次标号为 1,2,3,第 i 个矩形的左下角格子坐标设为 (Pi,Qi),右上角格子坐标设为 (Gi,Hi),要求满足:
- Pi≤Gi,Qi≤Hi;
- P1=P3>u+W,G1=G3;
- Q1=H1=Q2−1,H2+1=Q3=H3;
- P1<P2≤G2<G1。
下图是一个 N
,O
,I
的例子:
另外,所有画的图形均不允许超过纸张的边界。现在小 E 想要知道,他能画出的最大幸运度是多少。
输入格式
第一行包含两个正整数 n 和 m ,分别表示矩阵的行数和列数。
接下来 n 行,每行有 m 个整数,第 i+1 行的第 j 个数表示格子 (j,n−i+1) 的幸运值。
输出格式
输出一个整数 T,表示小 E 能够获得的最大幸运度。
3 13
1 1 -1 -1 1 -1 1 1 1 -1 1 1 1
1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 -1
1 -1 -1 1 1 -1 1 1 1 -1 1 1 1
24
3 13
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-20
提示
样例解释 1
样例解释 2
数据范围
测试点编号 |
n |
m |
幸运值范围 |
1 |
=3 |
=12 |
[−50,50] |
2 |
3 |
4 |
5 |
≤10 |
≤20 |
6 |
7 |
8 |
9 |
≤150 |
≤500 |
=1 |
10 |
11 |
≤80 |
[−200,200] |
12 |
13 |
14 |
15 |
≤150 |
≤500 |
16 |
17 |
18 |
19 |
20 |
对于所有的测试数据,保证 n≥3,m≥12。