D - 庭園
Editorial
/ 
/ 
Time Limit: 2.525 sec / Memory Limit: 246 MB
問題文
dwango社は広い庭を持っています。この庭は南北にH行・東西にW列の1m四方の区画に分かれています。 北から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行に出力せよ。出力の末尾にも改行をいれること。
入力例1
3 3 1 1 1 1 1 1 1 1 1
出力例1
9
2つの長方形で庭全体を覆うと、きれいさは最大の9となります。
入力例2
3 3 -1 -1 -1 -1 -1 -1 -1 -1 -1
出力例2
-2
残念ながらきれいさが負となるときもあります。長方形は少なくとも1つの区画を含まなければいけないことに注意してください。
入力例3
2 3 5 -1 8 -1 4 -1
出力例3
16
例えば、以下のような囲み方があります。
入力例4
4 4 5 2 -3 2 3 8 -3 -10 4 5 3 2 -5 -3 3 5
出力例4
40