問題一覧 > 通常問題

No.1095 Smallest Kadomatsu Subsequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 224
作問者 : SSRSSSRS / テスター : platinumplatinum
8 ProblemId : 4386 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-10-14 23:42:58

問題文

$3$つの要素からなる数列$A,B,C$で、以下の条件を満たすものを門松列といいます。

  • $A,B,C$のうちどの2つも異なる
  • $A,B,C$のうち、$B$が最も大きいか最も小さい
    • ある門松列$A,B,C$に対し、$A+B+C$をその大きさとします。
    また、ある数列の要素数$3$の部分列(連続でなくてもよい)で門松列であるものを部分門松列といいます。

    要素数$N$で、どの$2$つの要素も等しくない数列$A_1,A_2,\cdots,A_N$が与えられます。
    この数列の部分門松列のうち大きさが最も小さいものの大きさを求めてください。
    ただし、数列$A_1,A_2,\cdots,A_N$に部分門松列が存在しない場合、-1と出力してください。

    入力

    $N$
$A_1 \ A_2 \ \cdots \ A_N$

    入力は以下の制約を満たします。

    • 入力はすべて整数
    • $3 \leq N \leq 2 \times 10^5$
    • $1 \leq A_i \leq 10^8 (1 \leq i \leq N)$
    • $A_i \neq A_j (1 \leq i < j \leq N)$

    出力

    数列$A_1,A_2,\cdots,A_N$の部分門松列のうち大きさが最も小さいものの大きさを出力してください。
    ただし、数列$A_1,A_2,\cdots,A_N$に部分門松列が存在しない場合、-1と出力してください。

    サンプル

    サンプル1
    入力
    4
1 2 4 3
    出力
    8

    数列$1,2,4,3$には、部分門松列が$2$つあります。

  • $1,4,3$
  • $2,4,3$
    • この$2$つの門松列の大きさはそれぞれ$8,9$なので、そのうち最も小さい数である$8$を出力します。

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

    サンプル3
    入力
    4
1 2 3 4
    出力
    -1

    数列$1,2,3,4$には部分門松列は存在しないので、-1を出力します。

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