結果

問題 No.2332 Make a Sequence
ユーザー lam6er
提出日時 2025-04-15 23:12:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,995 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 133,600 KB
最終ジャッジ日時 2025-04-15 23:16:07
合計ジャッジ時間 18,009 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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
    
    # Check if B can be formed by concatenating prefixes of A
    # Compute max_k for each position in B using Z-algorithm
    X = -10**18  # A unique separator
    S = A + [X] + 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
    
    len_A = len(A)
    max_k = [0] * M
    for i in range(M):
        pos = len_A + 1 + i
        if pos >= n:
            max_k[i] = 0
        else:
            max_k[i] = Z[pos]
    
    # Now compute DP
    INF = 1 << 60
    dp = [INF] * (M + 1)
    dp[0] = 0
    heap = []
    heapq.heappush(heap, (0, 0))
    
    while heap:
        cost, i = heapq.heappop(heap)
        if i == M:
            print(cost)
            return
        if cost > dp[i]:
            continue
        if i >= M:
            continue
        # Compute k_max
        k_max = min(max_k[i], N, M - i)
        if k_max <= 0:
            continue
        # Iterate k from 1 to k_max
        for k in range(1, k_max + 1):
            j = i + k
            if j > M:
                break
            new_cost = cost + k * C[i]
            if new_cost < dp[j]:
                dp[j] = new_cost
                heapq.heappush(heap, (new_cost, j))
    
    print(-1)

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