結果

問題 No.2759 Take Pictures, Elements?
ユーザー LyricalMaestro
提出日時 2025-01-18 19:56:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 97 ms / 2,000 ms
コード長 952 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 82,884 KB
実行使用メモリ 76,556 KB
最終ジャッジ日時 2025-06-20 13:22:06
合計ジャッジ時間 2,460 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #

## https://yukicoder.me/problems/no/2759

MAX_INT = 10 ** 18

def main():
    N, Q = map(int, input().split())

    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    dp = [MAX_INT] * N
    dp[0] = 0

    for b in B:
        new_dp = [MAX_INT] * N

        # forward_min
        forward_min_list = [0] * N
        forward_min = MAX_INT
        for i in range(N):
            forward_min = min(-i + dp[i], forward_min)
            forward_min_list[i] = forward_min
        
        # backward_min
        backward_min_list = [0] * N
        backward_min = MAX_INT
        for i in reversed(range(N)):
            backward_min = min(backward_min, i + dp[i])
            backward_min_list[i] = backward_min

        for i in range(N):
            if A[i] == b:
                new_dp[i] = min(i + forward_min_list[i], backward_min_list[i] - i)
        dp = new_dp
    print(min(dp))





if __name__ == "__main__":
    main()
0