第2回早稲田大学プログラミングコンテスト

C - 至高のケーキ


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB

 今日もまた,きっと誰かの誕生日だ.ここでは,とあるイチゴが苦手な人の誕生日ケーキにまつわる次の問題に答えて欲しい.

問題

 ある人の誕生日ケーキを考える.誕生日ケーキは NM 列から成り,N×M個の正方形に切り分けることができる.各正方形には「効用」が設定されており,ある人がその部分のケーキを食べた時どれだけ満足度を得られるか,が決まっている.彼が最終的に得られる満足度は,切り分けた正方形の効用の合計である.また,ケーキの一部はイチゴを含むことがある.

 ここでは,誕生日ケーキを文字列で表すことにする.ケーキの各部分は文字で表す.ここで,各文字の意味は次のとおりである.
 0, 1, 2, ..., 9 : 書かれた数値の効用が得られる部分
 X : イチゴを含む部分
 ここで,ある人に誕生日ケーキを切り分けることを考える.その人は階段上の形が好きなので,図 1 に示すような階段上の形のケーキを 1 つだけ切り分け,彼に与える.正方形 1 つの形も階段状であるとみなす.ただし,彼はいちごがとても苦手なので,いちごを含む部分は切り分けないようにしたい.例えば,図 2 のようにいちごを含むような切り分け方はできない.

 ケーキの効用といちごの場所が与えられるので,彼が得られる満足度の最大値を求めよ.  
図1: ケーキの切り分け方

図2: 無効な切り分けの例

     

入力

入力は以下の形式で標準入力から与えられる.
N M
c_{1,1}c_{1,2} ... c_{1,M}
c_{2,1}c_{2,2} ... c_{2,M}
...
c_{N,1}c_{N,2} ... c_{N,M}
  • 1 行目にケーキの大きさを表す N(1 ≦ N ≦ 30) と M(1 ≦ M ≦ 30) が半角スペース区切りで与えられる.
  • 2 行目から N+1 行目には,M 文字の文字列が与えられる.これらケーキの効用値,あるいはいちごを表すデータである.
  • 文字列中に出現する文字列は '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'X' のいずれかであり,意味は上に記した通りである.
  • ケーキの文字列の中に出現する 'X' の数は N × M より少ないことを仮定してよい.

出力

彼が得られる満足度の最大値を1行に出力せよ.
なお、最後には改行を出力せよ.

入力例 1

3 3
433
333
333

出力例 1

19
例えば,
433
33
3
という部分を切り分けることにより,効用 19 が得られる.

入力例 2

3 5
11111
1X1X1
11111

出力例 2

3
このケースの場合,いちごがあるため,大きさ 3 以上のケーキは切り分けられない.よって,例えば
 1
11
という部分を切り分けることにより,効用 3 が得られる.

Submit提出する