A - コンテスト Editorial by Kiri8128
\({\rm DP}[i][j]\): \(i\) 番目まで見て \(j\) 点を取ることが可能か(可能なら \(1\) 、不可能なら \(0\) )
のようなDPを考えます。 \(M = \max(p_i)\) とすると、状態数が \(O(N^2 \times M)\) で各状態を \(O(1)\) で更新できるので、全体で \(O(N^2 \times M)\) で問題を解くことができます。
この遷移は bit 演算で高速化することもできます。
AC コード(Python 3) (配列で DP)
AC コード(Python 3) (bit 演算)
posted:
last update: