問題一覧 > 通常問題

No.1095 Smallest Kadomatsu Subsequence

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 232
作問者 : SSRS / テスター : platinum
お気に入りにしたユーザー ProblemId : 4386 / 自分の提出
問題文最終更新日: 2020-10-14 23:42:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 254 (順位表) の他の問題:

Problem Statement

A sequence $A,B,C$ of $3$ elements is called a Kadomatsu sequence if it satisfies the following conditions.

  • Any 2 of $A,B,C$ are different
  • Among $A,B,C$, $B$ is the largest or the smallest
    • For a Kadomatsu sequence $A,B,C$, we call $A+B+C$ its size.
    Also, a subsequence of $3$ elements of a sequence (not necessarily contiguous) that is a Kadomatsu sequence is called a Kadomatsu subsequence.

    You are given a sequence $A_1,A_2,\cdots,A_N$ of $N$ elements, in which no $2$ elements are equal.
    Find the size of the smallest-sized Kadomatsu subsequence of this sequence.
    However, if the sequence $A_1,A_2,\cdots,A_N$ has no Kadomatsu subsequence, output -1.

    Input

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

    The input satisfies the following constraints.

    • All input values are integers
    • $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)$

    Output

    Output the size of the smallest-sized Kadomatsu subsequence of the sequence $A_1,A_2,\cdots,A_N$.
    However, if the sequence $A_1,A_2,\cdots,A_N$ has no Kadomatsu subsequence, output -1.

    Sample

    Sample 1
    Input
    4
1 2 4 3
    Output
    8

    The sequence $1,2,4,3$ has $2$ Kadomatsu subsequences.

  • $1,4,3$
  • $2,4,3$
    • The sizes of these $2$ Kadomatsu sequences are $8,9$ respectively, so output the smallest of them, $8$.

    Sample 2
    Input
    5
1 4 6 2 3
    Output
    7

    Sample 3
    Input
    4
1 2 3 4
    Output
    -1

    The sequence $1,2,3,4$ has no Kadomatsu subsequence, so output -1.

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