部分点 2 (\(N \le 3000 \)) の解法を説明します。

区間が \(r_i\) 昇順にソートされているものとして、最後に \(N!\) を掛けます。

区間を順に見て行き、採用できるなら採用する、という貪欲法で最大値が求まります。

dp[区間を何個見たか][最後に採用した区間の右端は 既に決まっている点の中で 何番目か] という挿入 DP を考えます。dp 内では (現状の場合の数, 場合の数すべての採用数の和) の組を管理します。

dp[i][j] から \(i\) 個目(0 - indexed) の区間を見る際の遷移は、採用する場合しない場合ともに一か所に遷移するので \(O(1)\) で計算できます。

よって、全体で \(O\left(N ^2\right)\) で解くことが出来ました。