(略解です。正式な解説は後日公開されます。)

\(W=0,1,\dots,N^2\) における答えが求まれば \(W \gt N^2\) の時の答えは greedy で計算できることが知られている。よって \(0 \leq W \leq N^2\) の範囲を DP する問題になる。素直に実装すると \(\mathrm{O}(N^3)\) を達成できて部分点を取れる。

そして、素直な実装にある枝刈りを入れると計算量を \(\mathrm{O}(N^2 \log N)\) に改善できて、満点を取れる。論文

• 2022 年に発見された新しい手法だが、擬似コードがわずか 3 行 (!) という非常に簡潔な枝刈りなので興味がある方は読んでみてください。