問題一覧 > 通常問題

No.2701 A cans -> B cans

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 62
作問者 : MagentorMagentor / テスター : hamamuhamamu hirayuu_ychirayuu_yc
0 ProblemId : 10272 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-29 21:52:24

問題文

$p=1,2,\dots,M$ について、独立に以下の問題を解いてください。

Magentor君は、空き缶 $0$ を $p$ 個持っています。

また、$N$ 個の店があり、$i$ 番目の店では空き缶 $0$ または空き缶 $i$ を合計 $A_i$ 個渡すと、 $B_i$ 個のジュース入りの缶 $i$ と交換してもらうことができます。ここで、$A_i>B_i$ が保証されます。

Magentor君は、$1$ 個のジュース入りの缶 $i$ を、ジュースを飲むことで $1$ 個の空き缶 $i$ にすることができます。このとき、$C_i$ の嬉しさを得ます。

Magentor君が得られる嬉しさの和の最大値を求めてください。

入力

$N\ M$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
$\vdots$
$A_N\ B_N\ C_N$
  • $1\leq N\leq 5000$
  • $2\leq M\leq 5000$
  • $1\leq B_i<A_i\leq M$
  • $1\leq C_i\leq 10^9$
  • 入力はすべて整数

出力

$M$ 行出力してください。

$i$ 行目には、$p=i$ としたときの答えを出力してください。

サンプル

サンプル1
入力
2 5
4 3 3
5 2 8
出力
0
0
0
9
18

$p=5$ のとき、はじめMagentor君は空き缶 $0$ を $5$ 個持っています。以下のようにすることで、嬉しさの和を $18$ にすることができます。

  • 店 $1$ で、$4$ 個の空き缶 $0$ を、$3$ 個のジュース入りの缶 $1$ と交換する。
  • $3$ 個のジュース入りの缶 $1$ を、$3$ 個の空き缶 $1$ にする。このとき、$9$ の嬉しさを得る。
  • 店 $1$ で、$1$ 個の空き缶 $0$ と $3$ 個の空き缶 $1$ を、$3$ 個のジュース入りの缶 $1$ と交換する。
  • $3$ 個のジュース入りの缶 $1$ を、$3$ 個の空き缶 $1$ にする。このとき、$9$ の嬉しさを得る。

どのようにしても嬉しさの和を $19$ 以上にはできないので、$p=5$ のときは $18$ が答えです。

サンプル2
入力
1 2
2 1 1000000000
出力
0
1000000000
サンプル3
入力
3 10
9 8 1
5 1 8
5 2 4
出力
0
0
0
0
8
8
8
16
16
16

空き缶 $1$ を店 $2$ や店 $3$ で交換してもらうことはできないことに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。