結果

問題 No.2332 Make a Sequence
ユーザー gew1fw
提出日時 2025-06-12 19:04:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,814 bytes
コンパイル時間 324 ms
コンパイル使用メモリ 83,028 KB
実行使用メモリ 141,716 KB
最終ジャッジ日時 2025-06-12 19:05:48
合計ジャッジ時間 21,338 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq

def main():
    sys.setrecursionlimit(1 << 25)
    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 M == 0:
        print(0)
        return
    
    # Compute Z-array for A + '#' + B
    S = A + [0] + B  # Using 0 as a separator (assuming 0 is not in A or B)
    n = len(S)
    Z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            Z[i] = min(r - i + 1, Z[i - l])
        while i + Z[i] < n and S[Z[i]] == S[i + Z[i]]:
            Z[i] += 1
        if i + Z[i] - 1 > r:
            l, r = i, i + Z[i] - 1
    
    # Precompute k_i for each i in B
    k_list = [0] * M
    for i in range(M):
        pos_in_S = N + 1 + i
        max_k = Z[pos_in_S]
        max_k = min(max_k, N)
        max_k = min(max_k, M - i)
        k_list[i] = max_k
    
    # Check if B can be formed
    # We'll handle this via the DP
    
    INF = float('inf')
    dp = [INF] * (M + 1)
    dp[0] = 0
    heap = []
    heapq.heappush(heap, (0, 0))
    
    while heap:
        current_cost, i = heapq.heappop(heap)
        if i == M:
            print(current_cost)
            return
        if current_cost > dp[i]:
            continue
        max_k = k_list[i] if i < M else 0
        max_k = min(max_k, M - i)
        if max_k == 0:
            continue
        for k in range(1, max_k + 1):
            j = i + k
            if j > M:
                continue
            new_cost = current_cost + k * C[i]
            if new_cost < dp[j]:
                dp[j] = new_cost
                heapq.heappush(heap, (new_cost, j))
    
    print(-1 if dp[M] == INF else dp[M])

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