AOJ 1176 : 輪番停電計画
Planning Rolling Blackouts | Aizu Online Judge
まず長方形を考えたとき、全体の和 - 長方形内の値の和が
抑制需要になり、s - 抑制需要が予備力となる。
予備力が0より小さいときは、それ以上分割しても結果は同じなので、
遷移する必要はない。
2つに分割したときに小さい方の予備力を取れば、
最大抑制需要に対する予備力が求められる。
愚直にやると無理そうということが分かるけど
状態:値を「長方形:何個の長方形が作れるか」と置くと、
h^2w^2 だけ計算すれば良いことになる
（左上のx, y、右下のx, yと持つ）。
遷移はO(h + w)で行い、あらかじめ長方形内の値の和を
持っておいてO(1)で遷移可能かチェックできるようにする。
メモ化DPで書いて、O(h^2w^2(h + w))
