\(A\) を降順ソートしておきます。

\(K\) 枚の選び方を \((B_1, B_2, ..., B_K)\) と表すことにします \( (1 \leq B_i \leq N, B_i \geq B_{i+1})\) 。

例えば、\(B = (1, 1, ..., 1)\) のとき美味しさの和が最大で、\((2, 1, ..., 1)\) が次に大きいです。

美味しさを減らす遷移を工夫することで、 \(O(N \log N + X \log X)\) で解けます。

具体的には、公式解説における「妥協」(本ユーザ解説では \(B_i\) に \(1\) 足す) に以下の条件を追加します。

• \(B_i\) を増やしたとすると、それ以降 \(j < i\) の \(B_j\) を増やすことができない
• \(j < i\) において、\(B_j < B_i\) になるような「妥協」はできない

まず、\(2\) つ目の条件は冒頭の \(B_i \geq B_{i+1}\) の通りです。

\(1\) つ目の条件によって、各状態は複数の状態から遷移しません(つまり重複が省けます)。

これらを達成するような遷移は以下の2つだけで良いです。

• \(B_i\) に \(1\) 足す (ただし \(B_{i-1} \geq B_i\) を保つ)
• \(i\) に \(i+1\) を代入後、\(B_i\) に \(1\) 足す (ただし \(i \leq K\) かつ \(B_{i-1} \geq B_i\) を保つ)

状態は、美味しさの和, \(i\) , \(B_{i-1}\) , \(B_i\) の \(4\) つをpriority_queueなどのデータ構造で管理します。

実装例(C++)