No.2026 Yet Another Knapsack Problem
タグ : / 解いたユーザー数 18
作問者 :
suisen
/ テスター :
chineristAC
問題文
$N$ 種類の品物があります。各 $i\ (1\leq i \leq N)$ について、$i$ 種類目の品物は $c _ i$ 個あり、重さは $i$、価値は $v _ i$ です。
品物は合計で $\displaystyle \sum _ {i = 1} ^ N c _ i$ 個ありますが、suisen 君はこの中から重さの総和が $N$ 以下となるようにいくつかの品物を選ぼうとしています。
全ての $k=1,\ldots,N$ に対して、suisen 君がちょうど $k$ 個の品物を選ぶ場合の、選んだ品物の価値の総和の最大値を求めてください。本問題の制約下においては、全ての $k=1,\ldots,N$ に対して、suisen 君が重さの総和が $N$ 以下となるようにちょうど $k$ 個の品物を選ぶことが可能であることが証明できます。
入力
$N$ $c_1\ v_1$ $c_2\ v_2$ $\vdots$ $c_N\ v_N$
- 入力は全て整数である
- $1\leq N \leq 2500$
- $1\leq c _ i \leq N$
- 特に、$c _ 1 = N$ が成り立つ
- $-10 ^ 9\leq v _ i \leq 10 ^ 9$
出力
$N$ 行にわたって出力してください。$k\ (1\leq k\leq N)$ 行目には、重さの総和が $N$ 以下となるようにちょうど $k$ 個の品物を選ぶ場合の、選んだ品物の価値の総和の最大値を出力してください。
サンプル
サンプル1
入力
6 6 -10 1 6 4 3 3 -1 5 4 2 0
出力
6 9 -1 -24 -34 -60
入力は次を表しています。
- 重さ $1$ の品物は $6$ 個あり、それぞれの価値は $-10$ です。
- 重さ $2$ の品物は $1$ 個あり、それぞれの価値は $6$ です。
- 重さ $3$ の品物は $4$ 個あり、それぞれの価値は $3$ です。
- 重さ $4$ の品物は $3$ 個あり、それぞれの価値は $-1$ です。
- 重さ $5$ の品物は $5$ 個あり、それぞれの価値は $4$ です。
- 重さ $6$ の品物は $2$ 個あり、それぞれの価値は $0$ です。
出力についての説明です。
重みの和が $6$ 以下となるように $1$ つの品物を選ぶとき、価値の総和が最大となるのは重さ $2$ の品物を $1$ つ選んだときで、その総和は $6$ となります。
$2$ つの品物を選ぶとき、価値の総和が最大となるのは重さ $2$ の品物と重さ $3$ の品物を $1$ つずつ選んだときで、その総和は $9$ となります。ここで、重さ $2$ の品物は $1$ つしかないので $2$ つ選ぶことは出来ないことに注意します。また、重さ $2$ の品物と重さ $5$ の品物を $1$ つずつ選ぶような選び方は個数の制約は満たしますが、重みの和が $7$ となり $6$ を超えてしまうため、許容されません。
$3$ つの品物を選ぶ場合は重さ $1,2,3$ の品物を $1$ つずつ選ぶのが最適であり、その価値の総和は $-1$ となります。価値の総和は負の値を取り得ることに注意してください。
$4,5,6$ つの品物を選ぶ場合の価値の総和の最大値はそれぞれ $-24,-34,-60$ であることが証明できます。
サンプル2
入力
10 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000
出力
1000000000 2000000000 3000000000 4000000000 5000000000 6000000000 7000000000 8000000000 9000000000 10000000000
オーバーフローに注意してください。
サンプル3
入力
6 6 1 1 2 1 4 1 8 1 16 1 32
出力
32 17 10 7 6 6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。