問題一覧 > 通常問題

No.2026 Yet Another Knapsack Problem

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : suisensuisen / テスター : chineristACchineristAC
1 ProblemId : 8042 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-03 03:32:23

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。