ABC060 D Simple Knapsack
Diff 1477.
特殊な制約に注目する
. 今回は↓の制約に注目する.
https://gyazo.com/4bdef13b043ff0cc38fb55305d10055a
さて,
$ w_i
がとりうる値は4種類しかない. ここで少し考えてみると, 同じ重さであれば価値の大きい順に選んでいった方が得であることがわかる(
JOI 11本選 B 古本屋(難易度6)
と同じ).
$ N
の制約が小さいので, それぞれの重さを何個とるか全探索することができる！
実装例:
https://atcoder.jp/contests/arc073/submissions/18827117