SRM636 Div2 Hard : ChocolateDividingHard

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13388

h×wのグリッドが与えられる。各グリッドには0~9の文字が欠かれている。このグリッドを、切り込みを入れて4×4に分割する。

それぞれのブロックの中のグリッドの数字の和の最小値を最大にする問題。

制約：h,w<=75

解法

上手く切り込み入れて和の最小値をk以上にすることが出来るかを判別。

縦の切り込みを全通り試して、k以上に出来るかを貪欲にやる。
判定は、累積和やったりして多分O(75^4logN)くらいで危ない気がしたけどなんか通った。