No.1460 Max of Min
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 :
shiomusubi496
/ テスター :
butsurizuki
タグ : / 解いたユーザー数 31
作問者 :
shiomusubi496
/ テスター :
butsurizuki
問題文最終更新日: 2021-04-03 09:29:59
注意
この問題は実行時間制限が厳しいので高速な言語を使用することを推奨します。(writer解はPython3ではTLE、PyPy3ではACすることを確認しています。)
問題文
長さ $K$ の正整数列 $B$ が与えられます。ここで、数列 $A$ を次のように定義します。
- $A_0, A_1, A_2, ... A_{K-1}$ は与えられる
- $K\leq i$ の任意の $i$ について、 $A_i=max(min(A_{i-K},B_0),min(A_{i-K+1},B_1),min(A_{i-K+2},B_2), ... min(A_{i-1},B_{K-1}))$
入力
$K\ N$
$A_0\ A_1\ A_2\cdots A_{K-1}$
$B_0\ B_1\ B_2\cdots B_{K-1}$
- $1\leq K\leq 1000$
- $0\leq N\leq 10^{18}$
- $-10^{18}\leq A_i\leq 10^{18}$
- $-10^{18}\leq B_i\leq 10^{18}$
- 入力は全て整数
出力
$A_N$ を一行に出力し、最後に改行してください。
サンプル
サンプル1
入力
2 3 3 1 4 2
出力
2
数列 $A$ は次のようになります。
$A_0=3$
$A_1=1$
$A_2=max(min(3,4),min(1,2))=3$
$A_3=max(min(1,4),min(3,2))=2$
よって $A_3=2$ なので、 $2$ を出力します。
サンプル2
入力
1 1000 6 8
出力
6
$A$ の要素は全て $6$ です。
サンプル3
入力
5 10 4390 3289 3280 8032 5814 8231 9107 3289 4361 1332
出力
4390
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。