ABC#005 D.おいしいたこ焼きの焼き方

その他

問題

N*Nの正方形のタコ焼き器が与えられ、各マスごとにおいしさが決められている。
店員がQ人いて、P[i]マス以下の長方形のマスを使って焼くことができる。
店員ごとに焼きあがるタコ焼きのおいしさの合計値の最大値を答える。

N<=50
Q,P<=N^2

考え方

任意の長方形の内部の合計値を高速に求められれば、nマスの時の合計値を求められるので、すべての可能な長方形の合計値について求めて、nマスの最大値を求めておける。
長方形の内部の合計値は、SummedAreaTableを使うと、O(1)で求められる。よってO(N^4)で解ける。