ここでは \(10\) 点分の部分点を解説します。 \(R\) が昇順であると仮定し、最後に \(N!\) を掛けることとします。

\(R\) が昇順であることから、貪欲法をベースとする動的計画法を行うことができます。

具体的には、例えば

\(\mathrm{dp}[\mathcal{今見ている区間が何番目}][\mathcal{最後の右端の位置}][\mathcal{最後の採用した右端の位置}]\)

を管理することで \(Ο(N^5)\) の解法が得られます。

他にも様々な状態の管理の仕方があり、 \(Ο(N^4)\) や \(Ο(N^6)\) などになり得ますが、想定よりオーダーが悪い場合も入力は \(50\) 通りしかないため、埋め込みによって AC を得ることができます。