問題一覧 > 通常問題

No.1678 Coin Trade (Multiple)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 : stoqstoq / テスター : akakimidoriakakimidori chocoruskchocorusk
4 ProblemId : 6813 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-10 21:32:25

前書き

本問を含む次の2問は、制約と実行時間制限のみが異なります。

Coin Trade (Single)
Coin Trade (Multiple)

問題文

yukiさんは国 $1,$ 国 $2,\dots,$ 国 $N$ をこの順に旅行する計画を立てています。

国 $i$ で使用されている硬貨の価値は、1枚あたり $A_i$ 円です。 さらにいくつかの国には他国の硬貨に興味のある人がおり、別の国で入手した硬貨と今いる国の硬貨を交換できます。

国 $i$ では、次の行動のうち0個以上を選んで任意の順に実行することができます。

  • $j > 0$ を選ぶ。 $A_i \times j$ 円を払い、国 $i$ の硬貨 $j$ 枚を入手する。
  • もし国 $B_{i1},B_{i2},\dots,B_{iM_i} \ (< i)$ の $M_i$ 種の硬貨のうちいずれかを所持しているならば、 その硬貨1枚と 国 $i$ の硬貨1枚とを交換できる。
    複数種類の硬貨を同時に交換できるが、同じ種類の硬貨2枚以上を国 $i$ の硬貨に交換することはできない。(21:32 文章を訂正)

しかし財布の容量には限界があるため、所持する硬貨が $K$ 枚を超えるような硬貨の入手は認められません(円は除く)。

上記の行動を終えた直後には毎回、所持している硬貨のうち0枚以上を円に換金することが可能です。 $A_i$ 円の価値の硬貨は $A_i$ 円に換金されます。

最適に行動した場合、旅行開始前と旅行終了後で円はいくら増えるでしょうか?その最大値を求めてください。

ただし円は十分多く持っているため途中で尽きることはないものとします。

入力

$N\ K$
$A_1\ M_1$
$B_{11}\ B_{12} \dots B_{1M_1}$
$A_2\ M_2$
$B_{21}\ B_{22} \dots B_{2M_2}$
$\vdots$
$A_N\ M_N$
$B_{N1}\ B_{N2} \dots B_{NM_N}$

  • 入力は全て整数
  • $1 \leq N \leq 5 \times 10^4$
  • $1 \leq K \leq 50$
  • $1 \leq A_i \leq 10^9$
  • $0 \leq M_i < i$
  • $\sum_{i=1}^{N} M_i \leq 5 \times 10^4$
  • $1 \leq B_{i1} < B_{i2} < \dots < B_{iM_i} < i \ (1 \leq i \leq N)$

出力

最適に行動した際の、旅行終了前と旅行終了後の円の差額の最大値を出力してください。

サンプル

サンプル1
入力
2 1
3 0

5 1
1
出力
2

国 $1$ で $3$ 円消費して国 $1$ の硬貨を入手し、その後国 $2$ の硬貨と引き換え換金すると、$5$ 円入手できます。
合計で $2$ 円得したため2を出力します。

サンプル2
入力
3 2
1 0

2 1
1
3 1
1
出力
3

国 $1$ で $2$ 円払って硬貨 $2$ 枚を入手し、国 $2,3$ で交換したのち換金するのが最適です。

サンプル3
入力
15 3
2 0

1 0

14 1
2
20 1
1
11 1
3
1 0

10 0

7 1
1
17 1
6
4 1
6
11 0

20 5
3 5 6 10 11
4 2
6 11
1 1
13
7 3
4 8 11
出力
96

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