inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ https://atcoder.jp/contests/abc441/tasks/abc441_f何番目の商品まで考慮したかとトータルの金額を状態にして、最大の価値を値にしたDPを考えると、計算量はなので、なんとか間に合います。 入力例1だと、最初は0円で価値も0なので、 [0, -∞, -∞, -∞, -∞, -∞, -∞, -∞] とします。商品1を買う買わないで、 [0, -∞, 5, -∞, -∞, -∞, -∞, -∞] となります。4つの商品までで、 [0, -∞, 5, 10, 10, 15, 15, 20] 最終的には、 [0, -∞, 5, 20, 10, 25, 30, 3… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F2026%2F01%2F20%2F185733" title="AtCoder Beginner Contest 441 F - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2026-01-20 18:57:33 rich https://inamori.hateblo.jp/entry/2026/01/20/185733 1.0 100%