ABC192 F Potion
$ kの値を全探索する. ちょうど$ Xのポーションが作れる必要十分条件は, $ X - sum($ sumは選んだポーション)が$ kで割り切れることであり, これを変形すると$ X \% k = sum \% kとなる. さらに$ sumは必ず$ k個の和の形になっていなければならない. よってこの条件を満たす$ sumを最大化すればよい. これは各$ kごとに, $ dp_{i,j,l} = $ i番目まで見て, $ j個の品物を選んでおり, 今の値を$ kで割った余りが$ lのときの総和の最大値 としてDPをしていけば求められる.
計算量は$ O(N^4)となり, $ N = 100なので怪しいように見えるが, 間に合う! よく考えてみると, 定数倍が$ \frac{1}{8}となることからも間に合いそうなことがわかる.