A Garden with Ponds (Hard)

2 secs 1024 MB
SSRS's icon SSRS

A Garden with Ponds (AOJ 1618, AOJ-ICPC 150 点) の制約強化版です。

問題文

H×WH \times W のマス目があります。以下、ii 行目 jj 列目 (1iH,1jW)(1 \leq i \leq H, 1 \leq j \leq W) のマス目をマス (i,j)(i,j) と呼びます。

マス (i,j)(i,j) には、整数 AijA_{ij} が書かれています。

マス目のある部分長方形 {(i,j)1uidH,1ljrW}\{(i,j)|1 \leq u \leq i \leq d \leq H, 1 \leq l \leq j \leq r \leq W\} は、以下の条件を満たすとき 良い 部分長方形であると呼びます。

  • 大きさは縦・横ともに 33 以上である。つまり、du2,rl2d-u \geq 2, r-l \geq 2 が成り立つ。
  • 長方形の外側に接するマスに書かれている値は、そうでないマスに書かれている値よりも大きい。つまり、(x1,y1),(x2,y2)(x_1,y_1), (x_2,y_2) をこの部分長方形内のマスとし、x1=u,x1=d,y1=l,y1=rx_1=u,x_1=d,y_1=l,y_1=r のいずれかが成り立ち、かつ u<x2<d,l<y2<ru<x_2<d,l<y_2<r が成り立つとき、Ax1y1>Ax2y2A_{x_1y_1}>A_{x_2y_2} である。

ある良い部分長方形 {(i,j)1uidH,1ljrW}\{(i,j)|1 \leq u \leq i \leq d \leq H, 1 \leq l \leq j \leq r \leq W\} の容量 VV を、以下のように定義します。

  • hh を、部分長方形内にあり i=u,i=d,j=l,j=ri=u,i=d,j=l,j=r のいずれかが成り立つマス (i,j)(i,j) についての AijA_{ij} の最小値とする。
  • V=h(du1)(rl1)i=u+1d1j=l+1r1AijV = h(d-u-1)(r-l-1) - \sum_{i=u+1}^{d-1}\sum_{j=l+1}^{r-1}A_{ij}

良い部分長方形の容量の最大値を求めてください。ただし、良い部分長方形が存在しない場合、00 を出力してください。

制約

  • 3H7003 \leq H \leq 700
  • 3W7003 \leq W \leq 700
  • 0Aij109(1iH,1jW)0 \leq A_{ij} \leq 10^9 (1 \leq i \leq H, 1 \leq j \leq W)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

H WH \ W

A11 A12  A1WA_{11} \ A_{12} \ \cdots \ A_{1W}

A21 A22  A2WA_{21} \ A_{22} \ \cdots \ A_{2W}

\vdots

AH1 AH2  AHWA_{H1} \ A_{H2} \ \cdots \ A_{HW}

出力

良い部分長方形の容量の最大値を出力してください。ただし、良い部分長方形が存在しない場合、00 を出力してください。

サンプル

入力1
5 5
8 7 6 4 10
7 1 3 9 1
3 4 8 1 1
4 2 2 9 3
8 4 2 10 2
出力1
2
入力2
5 5
6 7 6 8 8
1 8 2 2 5
1 6 5 3 1
8 3 6 8 1
2 8 0 3 5
出力2
0

提出


Go (1.21)