問題一覧 > 通常問題

No.2759 Take Pictures, Elements?

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 87
作問者 : matcharate12 / テスター : 👑 binap aplysiaSheep
お気に入りにしたユーザー ProblemId : 7056 / 自分の提出
問題文最終更新日: 2024-05-17 11:43:59
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 430 (順位表) の他の問題:
Story
Today is the school trip. Latte has brought along an old single-lens reflex camera that looks rather expensive.
However, this camera has quite a narrow shooting range. Even so, in order to create youthful memories, he absolutely wants to capture his best friends in pictures.
It is troublesome, but he will spare no effort to photograph each of his best friends one by one, so he has decided to do his best to take the pictures.

Problem Statement

There are $N$ boxes $A$. The $i$-th box from the left is called box $i$, and the element inside box $i$ is called $A_i$. There is also a machine that refers to any $1$ of these boxes, and the machine is currently pointing at box $1$.
This machine can be moved to the box immediately to the right (if it exists) or the box immediately to the left (if it exists). The machine is also equipped with a mechanism for photographing the contents of a box.

Strictly speaking, Latte can perform any of the following operations independently.

  • For $1\le i\le N$, choose one of the following and decide whether to perform the operation. Performing it costs $1$, and not performing it costs nothing.
    • If $2\le i\le N$, move to box $i-1$.
    • If $1\le i\le N-1$, move to box $i+1$.
  • When the machine is referring to box $x$, photograph the element of box $x$. This costs nothing.

  • By repeatedly performing the above operations from now on, he wants to photograph $Q$ elements $B_1,B_2,\dots,B_Q$ using the machine (under the constraints of this problem, it is guaranteed that all the elements can be photographed by moving the machine).
    Note that after performing an operation $1$ time, the position the machine refers to carries over. See the sample input and output for details.

    What is the minimum possible total cost required to photograph $B_1,B_2,\dots,B_Q$ in this order?

    Input and Constraints

    $N\ Q$
    $A_1\ A_2\ \dots\ A_N$
    $B_1\ B_2\ \dots\ B_Q$
    

    • $1\le N\le 10^3$
    • $1\le Q\le 10^3$
    • $1\le A_i,B_j\le 10^9$
    • For every $1\le j\le Q$, there exists (at least one) $k$ such that $B_j=A_k$
    • All input values are integers

    Output

    Output the answer.

    Sample

    Sample 1
    Input
    5 4
    3 7 1 9 2
    1 2 3 7
    
    Output
    9

    • To capture $1$, move right exactly $2$ times from box $1$ and take a picture. The required cost is $2$, and the current position is box $3$.
    • To capture $2$, move right exactly $2$ times from box $3$ and take a picture. The required cost is $2$, and the current position is box $5$.
    • To capture $3$, move left exactly $4$ times from box $5$ and take a picture. The required cost is $4$, and the current position is box $1$.
    • To capture $7$, move right exactly $1$ time from box $1$ and take a picture. The required cost is $1$.
    With these operations, the total cost is $2+2+4+1=9$. It is impossible to operate so that the total is $8$ or less.

    Sample 2
    Input
    3 5
    7 1 10
    7 7 7 7 7
    
    Output
    0

    There are cases where all the elements can be photographed without any movement at all.

    Sample 3
    Input
    3 2
    1 1 2
    2 1
    
    Output
    3
    Note that the elements of $A_i,B_i$ are not necessarily pairwise distinct.

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