問題一覧 > 通常問題

No.2182 KODOKU Stone

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : MasKoaTSMasKoaTS / テスター : 👑 potato167potato167 ShirotsumeShirotsume
2 ProblemId : 8404 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-28 20:47:24

問題文

$1,2,\dots,N$ の番号が付いた $N$ 個の袋と中に何も入っていない $1$ 個の箱があります。
袋 $i$ $(1 \leq i \leq N)$ には $T_{i}$ 個の石が入っており、このうち $j$ $(1 \leq j \leq T_{i})$ 番目の石の質量は $A_{i,j}$ です。

コアさんは、これらの袋と石と箱を用いて、$i=1,2,\dots,N$ の順に次の操作を行います。

  1. まず、石が $1$ 個以上入っている袋を自由に $1$ 個選び、その中の石をすべて箱の中に入れる。

  2. 次に、箱の中にある石の個数を $n$ として、これら $n$ 個の石のうち、次の条件を満たすものの中から無作為に $1$ 個選ぶ。
    ここで、$x = \min(K_{i}, n)$ とする。

    • $n$ 個の石の質量が降順に $a_{1}, a_{2}, \dots, a_{n}$ $(a_{1} \geq a_{2} \geq \cdots \geq a_{n})$ と表されるとき、自身の質量が $a_{x}$ に等しい。

  3. 最後に、選んだ石以外の $n-1$ 個の石をすべて箱の中から取り出して食べる。

すべての $i$ に対して操作を終了した後、箱の中に残るただ $1$ 個の石の質量としてあり得るものの最大値を求めてください。

制約

  • $1 \leq N \leq 10^{5}$

  • $1 \leq T_{i} \leq 10^{5}$ $(1 \leq i \leq N)$

  • $T_{1}, T_{2}, \dots, T_{N}$ の総和は $10^{5}$ 以下

  • $1 \leq A_{i,j} \leq 10^{9}$ $(1 \leq i \leq N \text{ かつ } 1 \leq j \leq T_{i})$

  • $1 \leq K_{i} \leq 3 \times 10^{5}$ $(1 \leq i \leq N)$

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$
$K_{1}$ $K_{2}$ $\cdots$ $K_{N}$
$T_{1}$
$A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,T_{1}}$
$T_{2}$
$A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,T_{2}}$
  $\vdots$
$T_{N}$
$A_{N,1}$ $A_{N,2}$ $\cdots$ $A_{N,T_{N}}$

  • $1$ 行目には $N$ が与えられる

  • $2$ 行目には $K_{1}, K_{2}, \dots, K_{N}$ がこの順に半角スペース区切りで与えられる

  • $2 i + 1$ $(1 \leq i \leq N)$ 行目には $T_{i}$ が与えられる

  • $2 i + 2$ $(1 \leq i \leq N)$ 行目には $A_{i,1}, A_{i,2}, \dots, A_{i,T_{i}}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
3
3 1 2
2
1 2
5
7 9 5 3 9
4
10 8 6 4
出力
9

例えば次の操作を考えることにより、最終的に質量 $9$ の石のみが箱の中に残ります。

  1. 袋 $1$ を選び、その中にある $2$ 個の石を箱の中に入れる。

  2. $x = \min(3,2) = 2$, $(a_{1}, a_{2}) = (2, 1)$ であり、箱の中にある $2$ 個の石のうち質量が $a_{2} = 1$ であるものの中から無作為に $1$ 個を選ぶ。
    そして、選んだ $1$ 個以外の $1$ 個をすべて箱の中から取り出して食べる。このとき、質量 $1$ の石が箱の中に残る。

  3. 袋 $2$ を選び、その中にある $5$ 個の石を箱の中に入れる。

  4. $x = \min(1,6) = 1$, $(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}) = (9, 9, 7, 5, 3, 1)$ であり、箱の中にある $6$ 個の石のうち質量が $a_{1} = 9$ であるものの中から無作為に $1$ 個を選ぶ。
    そして、選んだ $1$ 個以外の $5$ 個をすべて箱の中から取り出して食べる。このとき、質量 $9$ の石が箱の中に残る。

  5. 袋 $3$ を選び、その中にある $4$ 個の石を箱の中に入れる。

  6. $x = \min(2,5) = 2$, $(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}) = (10, 9, 8, 6, 4)$ であり、箱の中にある $5$ 個の石のうち質量が $a_{2} = 9$ であるものの中から無作為に $1$ 個を選ぶ。
    そして、選んだ $1$ 個以外の $4$ 個をすべて箱の中から取り出して食べる。このとき、質量 $9$ の石が箱の中に残る。

質量が $9$ より大きい石を箱の中に残すことはできません。

サンプル2
入力
5
2 2 2 1 2
1
1
1
10
1
100
1
1000
1
10000
出力
1000
サンプル3
入力
9
4 2 10 7 3 300000 7 1 5
5
7 1433 233 441445814 14
8
84906649 75121583 12 603415 10147 199004 65221 151278232
7
129002 468 235 250 1144 38994 1070804
10
122230317 19048460 168635 817 24296790 17 6404 49328 194386 61986
5
18 11 408 1 2
1
7
10
339112 57 159599 209673 234036624 277265898 34115930 17787 13825 20151
9
16 2337 557 185983 823 47160 712213 20538 100
3
829 10 9307
出力
603415

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