時間制限:4000ミリ秒
メモリ制限:65536KB
行列の分割
問題
非負の要素のみからなる M * N の行列が与えられ、あなたはこれを2つの線分を用いて3つの部分に分割する。線分は行列の要素の上をまたぐことはなく、かつ行列の列または行に対して平行でなければならない。また、2つの線分同士は平行であってはならない。3つの部分は空でない行列、つまり1つ以上の要素を含む行列である。ここでは、行列の値を、行列の要素の合計値として定義する。3つの行列の値をX,Y,Zとおいて、バランス度数を|X-Y|+|Y-Z|+|Z-X|(||は絶対値)で定義する。全ての分割パターンのうち、最小のバランス度数をもつものが存在する。あなたの仕事は、最小のバランス度数を決定することである。
入力
入力はいくつかのテストケースからなる。各テストケースについて、2つの整数M,Nが最初の行で与えられる。これは行列の列と行の数を意味する。続くM行はN個の整数を含み、行列をあらわす。入力は2つのゼロを含む行からなる。2<=M,N<=500かつ、全ての行列の要素は0以上65535以下の整数である。
テストケースの間にはいくつかの空行があるかもしれない。
出力
入力された行列について、それぞれ最小のバランス度数を含む1行を出力せよ。
入力例
3 3 9 8 7 6 5 4 3 2 1 0 0
出力例
10
ヒント
入力例における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である。これがあなたが得られる最小のバランス度数である。
出典
POJ Monthly,c0500301036