結果

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

ソースコード

diff # 

MOD = 10**18 + 3
BASE = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N, M = int(data[ptr]), int(data[ptr+1])
    ptr += 2
    A = list(map(int, data[ptr:ptr+N]))
    ptr += N
    B = list(map(int, data[ptr:ptr+M]))
    ptr += M
    C = list(map(int, data[ptr:ptr+M]))
    ptr += M
    
    # Compute hash for A
    ha = [0] * (N + 1)
    power_a = [1] * (N + 1)
    for i in range(N):
        ha[i+1] = (ha[i] * BASE + A[i]) % MOD
        power_a[i+1] = (power_a[i] * BASE) % MOD
    
    # Compute hash for B
    hb = [0] * (M + 1)
    power_b = [1] * (M + 1)
    for i in range(M):
        hb[i+1] = (hb[i] * BASE + B[i]) % MOD
        power_b[i+1] = (power_b[i] * BASE) % MOD
    
    k_max = [0] * M
    
    for i in range(M):
        if B[i] != A[0]:
            continue
        max_len = 0
        low = 1
        high = min(N, M - i)
        while low <= high:
            mid = (low + high) // 2
            if i + mid > M:
                high = mid - 1
                continue
            hash_a = (ha[mid] - ha[0] * power_a[mid]) % MOD
            hash_b_part = (hb[i + mid] - hb[i] * power_b[mid]) % MOD
            if hash_a == hash_b_part:
                max_len = mid
                low = mid + 1
            else:
                high = mid - 1
        k_max[i] = max_len
    
    INF = 1 << 60
    dp = [INF] * (M + 1)
    dp[0] = 0
    
    for i in range(M):
        if dp[i] == INF:
            continue
        max_k = k_max[i]
        for k in range(1, max_k + 1):
            j = i + k
            if j > M:
                continue
            if j > M:
                break
            cost = k * C[i]
            if dp[j] > dp[i] + cost:
                dp[j] = dp[i] + cost
    
    if dp[M] == INF:
        print(-1)
    else:
        print(dp[M])

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