notorious coincidence

真面目に書くと大変なので雑です．

まずオリジナルの問題のテストケースがそのまま与えられているときのことを考えます．

人の集合を決めたら \(B_i\) の降順に使うとしてよいです． そして，操作を後ろから見てみます． 詳細は省きますが，ここで考察を行うと，問題は以下のような貪欲に帰着されます．

• priority queue \(P\) を管理する．\(P\) は最小の要素が top にある．
• 便利のため，\(P\) には最初 \(\infty\) が入っているものとする．
• \(B_i\) が昇順に並んでいるとし，\(i=1,2,...N\) について以下の操作を行う．
• \(d=B_i-B_{i-1}\) とする．\(P\) の要素を小さい方から削っていく．削った総量が \(d\) になるところで止まる． \(P\) から pop した値の個数が \(k\) になったタイミングで今までに削った総量が \(k\) 人選ぶときの問題の答えになる．
• \(P\) に \(A_i\) を追加する．

これを DP で数え上げにします． 普通に priority queue の状態を持つと状態数が多すぎるので工夫します． \(A_i\) を追加するタイミングで，この \(A_i\) は最初の \(k\) 回で pop されるべきか否か，というものを決め打つと，priority queue の状態としては，

• pop されるべきとした値の個数
• pop されるべきものの値の和
• pop されるべきものの値の max
• pop されないべきものの値の min

を持てばよいです． これで DP すれば \(O(N^3V^4)\) で計算できます．