ABC005 D - おいしいたこ焼きの焼き方

D - おいしいたこ焼きの焼き方

提出コード
mp[i][j] = からまでの、長方形の部分の美味しさの総和
(ただし、添え字が0以下のときは0)
として、入力と同時に累積和をとっていきます。
すると、ある長方形をl,r,u,d(それぞれ長方形の左、右、上、下の辺の番号)で表すと、その部分の美味しさの総和は
mp[d][r]+mp[u-1][l-1]-mp[u-1][r]-mp[d][l-1]
となるので、あとはl,r,u,dを動かして全探索します(包除原理のような感覚です)。
全探索して求めた美味しさの総和を、マス目の数でわけてそれぞれの最大値をとり、クエリにこたえていけば完了になります。