選ぶ格子点の凸包の右上 ¹⁄₄ 部分が決まれば，選ぶ格子点の集合が自動的に定まる． したがって，入力格子点を辞書順（昇順）に見ながら，この右上部分を構成する直前の \(2\) 点を持って DP すればよい． 具体的には，\(\mathrm{dp}(p, q)\) を「凸包の右上部分を構成する最後の線分が \((p, q)\) である場合の最適値」として，以下のように更新していけばよい．（凸包の右上部分の線分の傾きは非正かつ単調減少であり，\(1\) 点目を追加するときは傾き \(0\) で \(Y\) 軸と交わる線分を取る必要があることに注意する．）

\[\mathrm{dp}(p_1, q) = \max_{p_2} \{\, \mathrm{dp}(p_2, p_1) + \mathrm{add}(p_1, q) \mid (p_2, p_1) の傾き \ge (p_1, q) の傾き \,\}\]

ここで \(\mathrm{add}(p_1, q)\) は新しく追加されるべき（線分 \((p_1, q)\) 以下の台形領域内の）格子点の得点の合計であり，これは今の点と直前の \(1\) 点のみに依存するため，愚直に全ペアについて前計算しておけばよい． 前計算と DP の遷移を素朴に実装すれば，全体の計算量は \(\mathrm{O}(N^3)\) となる．