まずは \(a_{i,j}\) を計算する. これはすべての黒い頂点をキューに入れて幅優先探索をすれば求められる.

ここで, \(E_{i,j}\) を, 「頂点 (i, j) が一番上になる三角形で, 三角形内の \(a_{i,j}\) の合計が \(P\) 以上になる最小の大きさ」と定義する. \(E_{i,j}\) が求まれば, \(E_{i,j}\) 以上の大きさの三角形は必ず条件を満たす.

\(E_{i,j}\) についてであるが, \(E_{i,j} \leq \min(E_{i+1,j}, E_{i+1,j+1})+1\) が成り立つ. よって, \(R = \min(E_{i+1,j}, E_{i+1,j+1})+1\) とおいて, \(E_{i,j}\) の範囲を狭めていけばいい.

なお, 指定された三角形の内部の合計であるが, 解説の図のような求め方をする.

緑の三角形と青の三角形の部分については, すべての頂点において, その頂点を一番上になる三角形で底辺が一番下の点を含むものを DP で求めておく.

青い平行四辺形部分については, 通常の長方形の累積和が使える.