[[原文:http://acm.pku.edu.cn/JudgeOnline/problem?id=2444]]
----
''時間制限'':4000ミリ秒
''メモリ制限'':65536KB
&br;

行列の分割

*問題 [#a7dc9cca]

非負の要素のみからなる M * N の行列が与えられ、あなたはこれを2つの線分を用いて3つの部分に分割する。線分は行列の要素の上をまたぐことはなく、かつ行列の列または行に対して平行でなければならない。また、2つの線分同士は平行であってはならない。3つの部分は空でない行列、つまり1つ以上の要素を含む行列である。ここでは、行列の値を、行列の要素の合計値として定義する。3つの行列の値をX,Y,Zとおいて、バランス度数を|X-Y|+|Y-Z|+|Z-X|(||は絶対値)で定義する。全ての分割パターンのうち、最小のバランス度数をもつものが存在する。あなたの仕事は、最小のバランス度数を決定することである。

*入力 [#x21cb7f2]

入力はいくつかのテストケースからなる。各テストケースについて、2つの整数M,Nが最初の行で与えられる。これは行列の列と行の数を意味する。続くM行はN個の整数を含み、行列をあらわす。入力は2つのゼロを含む行からなる。2<=M,N<=500かつ、全ての行列の要素は0以上65535以下の整数である。

テストケースの間にはいくつかの空行があるかもしれない。

*出力 [#w6605b48]

入力された行列について、それぞれ最小のバランス度数を含む1行を出力せよ。

*入力例 [#e971f807]

 3 3
 9 8 7
 6 5 4
 3 2 1
 0 0

*出力例 [#f6cc9c0e]

 10

*ヒント [#q5cfc953]

入力例における3分割は、{9,8}, {6, 5, 3, 2}, {7, 4, 1}であり、これらの行列の値は、9+8=17, 6+5+3+2=16, 7+4+1=12である。これに対応するバランス度数は、|17-16|+|16-12|+|12-17|=10である。これがあなたが得られる最小のバランス度数である。

*出典 [#c335cbbf]

POJ Monthly,c0500301036