問題一覧 > 通常問題

No.861 ケーキカット

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : testestesttestestest
5 ProblemId : 2254 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-10-25 18:19:49

問題文

5行5列のサイズの正方形のケーキがありA君とB君の2人で分けます。

ケーキの$i$行目$j$列目には美味しさ$C_{ij}$が決められています。
$i$行目$j$列目のケーキはA君かB君かいずれかのものになります。

さて、ケーキをカットしてから2人に分けることにします。
カットは行と行の間、列と列の間でカットできますが、ここで条件があります。

A君、B君に行き渡るそれぞれのケーキの部分は2つに切り分け、それぞれ連結でなければいけません。
(連結とはあるi行j列目のケーキ部分に辺で接する隣り合うケーキ部分が切り離されないことをいう。)

A君とB君にケーキが残らずに行き渡った時、それぞれの美味しさの合計の差を最小にしたいです。
最小になるように切ったとき、その差を(負でない整数で)求めよ。

入力

$C_{00}$ $C_{01}$ $C_{02}$ $C_{03}$ $C_{04}$
$C_{10}$ $C_{11}$ $C_{12}$ $C_{13}$ $C_{14}$
$C_{20}$ $C_{21}$ $C_{22}$ $C_{23}$ $C_{24}$
$C_{30}$ $C_{31}$ $C_{32}$ $C_{33}$ $C_{34}$
$C_{40}$ $C_{41}$ $C_{42}$ $C_{43}$ $C_{44}$

$C_{ij}$は$i$行$j$列目のケーキの美味しさ。
$C_{ij}$は正の整数。$1 \le C_{ij} \le 1000000000=10^9$

出力

答えを1行で出力せよ。
最後に改行してください。

サンプル

サンプル1
入力
3 5 4 1 6
6 3 4 3 1 
3 2 4 7 6
4 5 6 2 1
1 4 3 5 2
出力
1

例えば下のような切り方があります。(赤い線が切るところです。)
2つに分けられたケーキはいずれも連結しています。

サンプル2
入力
8 2 4 3 1
3 3 8 7 2
1 3 6 6 2
4 5 9 2 5
2 3 3 4 2
出力
0

下のようなドーナツ状の切り方もできます。

サンプル3
入力
200 3 2 1 5
5 15 4 5 6
7 6 5 1 7
3 10 2 3 11
2 4 1 6 10
出力
76

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。