D - 庭園

Contest Duration: 2016-01-23(Sat) 11:00 - 2016-01-23(Sat) 13:00 (local time) (120 minutes)

D - 庭園 Editorial

Time Limit: 2.525 sec / Memory Limit: 246 MB

問題文

dwango社は広い庭を持っています。この庭は南北に $H$ 行・東西に $W$ 列の $1$ m四方の区画に分かれています。北から $i$ 、西から $j$ 番目にある区画を区画 $(i,j)$ と表すことにします。庭にはたくさんの花が咲いており、それぞれの区画についてその区画にある花の見栄えのよさを表す整数が定まっています。区画 $(i,j)$ の花の見栄えのよさを $B_{i,j}$ と表すことにします。

少なくとも1つの区画からなる長方形を2つ決め、その2つの長方形を柵で囲い、柵で囲われていない場所を道にすることで、庭をきれいなものにしようとと考えました。ここで、2つの長方形の両方に含まれる区画があってはいけませんが、柵が重なるのは問題ありません。

庭全体のきれいさは、どちらかの長方形で囲われている区画の見栄えのよさの総和です。

理想の庭園を作るため、まずきれいさの最大値を求めることとなりました。庭全体のきれいさの最大値を求めるプログラムを作成してください。

入出力

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

 $H$   $W$ 
 $B_{1,1}$   $B_{1,2}$  …  $B_{1,W}$ 
:
 $B_{H,1}$   $B_{H,2}$  …  $B_{H,W}$

$1$ 行目には、それぞれ庭園の南北、東西方向の長さである $H, W (2 ≦ H ≦ 300, 2 ≦ W ≦ 300)$ が空白区切りで与えられる。
$1+i (1 ≦ i ≦ H)$ 行目には、北から $i$ 番目の区画の見栄えのよさを表す $W$ 個の整数 $B_{i,1}, ...,B_{i,W}$ が空白区切りで与えられる。
$-10^9≦B_{i,j}≦10^9 (1 ≦ i ≦ H, 1 ≦ j ≦ W)$ が成り立つ。

配点

この問題には部分点が設定されている。

$H ≦ 50, W ≦ 50$ を満たすデータセットに正解した場合は $50$ 点が与えられる。
全てのテストケースに正解した場合は、上記とは別に $50$ 点が与えられる。

出力

2つの長方形を決めたときの、庭全体のきれいさの最大値を $1$ 行に出力せよ。出力の末尾にも改行をいれること。

入力例1Copy

Copy

出力例1Copy

Copy

$2$ つの長方形で庭全体を覆うと、きれいさは最大の $9$ となります。

入力例2Copy

Copy

3 3
-1 -1 -1
-1 -1 -1
-1 -1 -1

出力例2Copy

Copy

-2

残念ながらきれいさが負となるときもあります。長方形は少なくとも1つの区画を含まなければいけないことに注意してください。

入力例3Copy

Copy

2 3
5 -1 8
-1 4 -1

出力例3Copy

Copy

例えば、以下のような囲み方があります。

https://discovery2016-qual.contest.atcoder.jp/img/other/dwango2016qual/hdfksjghkjsdfhgkjsdhfgkjs/problem2.PNG

入力例4Copy

Copy

出力例4Copy

Copy