公式解説 とほぼ同様ですが、 価値 を直接整数で管理し、 popcount （\(2\) 進法で \(1\) が立っている箇所の個数を調べる関数）を使うとより簡単かつ高速な実装ができます。

本問ではタイプごとの価値は \(2\times\mathrm{max }(S_i)\times \mathrm{max}(C_i)=2\times 10^{18}<2^{61}\) 未満なので、 \(64\) ビット整数で表せます。この範囲内では、 \(n\) の popcount は \(O(\log\log n)\) などで計算できます。全体の計算量は Dict や popcount の計算量によって、 \(O(N\log N)\) や \(O(N\log\log N)\) などになります。