点の集合 \(A\) を整列して得られる列の個数を \(f(A)\) と置くことにします． ここで，\(A\) の \(X\)座標や\(Y\)座標は順列に限らないものとします． ただし実際に \(f\) の値を求める際には，座標圧縮を行って順列にしてから計算します．

基本的な方針では，\(A\) をどの位置でどの方向に沿って分割するかを全部試し，\(f\) を再帰的に呼んで計算を行います． ただし，これでは同じ列を複数回数えてしまうことがあります．

これは，目標となる列を決め打っても，\(A\) をどのように分割するかに自由度があるためです． そこで，以下のようなルールで \(A\) に対して行う分割を一意に定めることにします．

• \(X\) 座標 \(x\) 未満かどうかで分割することを \(X_x\) と表すことにする．同様に，\(Y\) 座標 \(y\) 未満かどうかで分割することを \(Y_y\) と表す．
• 目標となる列を得られる分割のうち，\(X_2,Y_2,X_3,Y_3,\cdots,X_K,Y_K\) の中で最も先頭に近いものを採用する．

分割の優先度順に，その分割が選ばれるような目標列の個数を考えます．

今，\(X_x\) に注目しているとします． ここで，上の手順で \(X_x\) が選ばれるかどうかは，目標列の先頭 \(x-1\) 個の様子で決まることに注意します． よって，そのような先頭 \(x-1\) 個の並べ方を数えることにします． まず\(X\)座標が\(x\)未満の点を整列して得られる列の個数を数えます． そこから，実際は上の手順で選ぶ分割が \(X_2,Y_2,X_3,Y_3,\cdots,X_{x-1},Y_{x-1}\) になるようなものを引きます． 例えば，\(X_z\) \((z < x)\)が選ばれるような列は，\((X_z\) が上の手順で選ばれるような先頭 \(z-1\) 個\()+(X\)座標が \(z\) 以上 \(x\) 未満の点の集合を整列して得られる列\()\)となります． ここで，\((X_z\) が上の手順で選ばれるような先頭 \(z-1\) 個\()\)の並べ方はすでに求めているはずなので，このような列の個数を数えることができます． \(Y\) 方向の分割についても同様に計算できます．

計算量を見積もります． \(f\) の引数に渡される点の集合は，入力で与えられた \(N\) 点の集合の矩形領域を切り取った形に限定されます． よってメモ化をすれば \(O(N^4)\) 状態しかありません． \(1\) 状態につき \(O(N^2)\) 時間で計算できるため，計算量は全体で \(O(N^6)\) になります．

実装が長いが定数倍の速い解答例(c++)

実装が簡潔だが定数倍の遅い解答例(c++)