結果

問題 No.2332 Make a Sequence
ユーザー lam6er
提出日時 2025-03-20 20:47:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,598 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 143,876 KB
最終ジャッジ日時 2025-03-20 20:48:03
合計ジャッジ時間 18,116 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    from bisect import bisect_left, bisect_right
    
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))
    
    if B[0] != A[0]:
        print(-1)
        return
    
    # Step 1: Compute Z-array for S = A + [separator] + B
    SEP = -1
    S = A.copy()
    S.append(SEP)
    S += B
    
    n = len(S)
    Z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i > r:
            l = r = i
            while r < n and S[r - l] == S[r]:
                r += 1
            Z[i] = r - l
            r -= 1
        else:
            k = i - l
            if Z[k] < r - i + 1:
                Z[i] = Z[k]
            else:
                l = i
                while r < n and S[r - l] == S[r]:
                    r += 1
                Z[i] = r - l
                r -= 1
    Z[0] = 0
    
    lenA = len(A)
    lenA_plus_1 = lenA + 1
    
    l_j = [0] * M
    for j in range(M):
        pos_in_S = lenA_plus_1 + j
        max_len = Z[pos_in_S]
        max_len = min(max_len, lenA)
        max_len = min(max_len, M - j)
        l_j[j] = max_len
    
    # Collect starts including 0 and positions where B[j] == A[0]
    starts = [0]
    for j in range(1, M):
        if B[j] == A[0]:
            starts.append(j)
    starts.append(M)
    starts.sort()
    
    # Preprocess for existence checks
    starts_set = set(starts)
    starts.pop()  # remove M
    
    # Initialize DP
    INF = float('inf')
    dp = {s: INF for s in starts}
    dp[0] = 0
    dp[M] = INF
    
    for i in range(len(starts)):
        j = starts[i]
        if dp[j] == INF:
            continue
        max_k = l_j[j]
        if max_k == 0:
            continue
        high = j + max_k
        # Find all s in starts where j < s <= high
        left = bisect_right(starts, j)
        right = bisect_right(starts, high)
        possible_s = starts[left:right]
        # Also check if high is M
        if high >= M:
            possible_s.append(M)
        for s in possible_s:
            if s > M:
                continue
            k = s - j
            if s == M:
                if dp[M] > dp[j] + k * C[j]:
                    dp[M] = dp[j] + k * C[j]
            else:
                if s in starts_set:
                    if dp[s] > dp[j] + k * C[j]:
                        dp[s] = dp[j] + k * C[j]
    
    if dp[M] != INF:
        print(dp[M])
    else:
        print(-1)

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