結果

問題 No.2332 Make a Sequence
ユーザー lam6er
提出日時 2025-04-15 23:12:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,510 bytes
コンパイル時間 411 ms
コンパイル使用メモリ 81,632 KB
実行使用メモリ 176,188 KB
最終ジャッジ日時 2025-04-15 23:15:08
合計ジャッジ時間 15,518 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    M = int(data[idx+1])
    idx +=2
    A = list(map(int, data[idx:idx+N]))
    idx +=N
    B = list(map(int, data[idx:idx+M]))
    idx +=M
    C = list(map(int, data[idx:idx+M]))
    
    if M == 0:
        print(0)
        return
    
    # Compute failure function for A
    failure = [0] * N
    for i in range(1, N):
        j = failure[i-1]
        while j > 0 and A[i] != A[j]:
            j = failure[j-1]
        if A[i] == A[j]:
            j += 1
        failure[i] = j
    
    # Compute max_k for each position in B
    max_k = [0] * M
    current_k = 0
    for i in range(M):
        while current_k > 0 and B[i] != A[current_k]:
            current_k = failure[current_k - 1]
        if B[i] == A[current_k]:
            current_k += 1
        max_k[i] = current_k
        if current_k == N:
            current_k = failure[current_k - 1]
    
    # Compute DP
    INF = float('inf')
    dp = [INF] * (M + 1)
    dp[0] = 0
    
    for i in range(1, M + 1):
        current_max_k = max_k[i-1]
        k = current_max_k
        while k > 0:
            prev = i - k
            if prev >= 0:
                cost = dp[prev] + k * C[prev]
                if cost < dp[i]:
                    dp[i] = cost
            # Move to next k in failure chain
            k = failure[k-1] if k > 0 else 0
    
    print(dp[M] if dp[M] != INF else -1)

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