結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N, M = int(data[idx]), 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]))
    
    # Precompute max_k for each position in B
    # Construct the concatenated string in a way that the prefix function can be applied
    # Each element is treated as a separate character, using a delimiter not present in A or B elements
    # Here, we use a string representation with a special separator
    def get_prefix_function(s):
        n = len(s)
        pi = [0] * n
        for i in range(1, n):
            j = pi[i-1]
            while j > 0 and s[i] != s[j]:
                j = pi[j-1]
            if s[i] == s[j]:
                j += 1
            pi[i] = j
        return pi
    
    # Create the combined string
    delimiter = '#'
    A_str = [str(x) for x in A]
    B_str = [str(x) for x in B]
    combined = delimiter.join(A_str) + '#' + delimiter.join(B_str)
    pi = get_prefix_function(combined)
    
    len_A = len(A_str)
    len_A_plus_delim = len(A_str) + 1  # including the delimiter
    max_k = [0] * (M)
    for i in range(len_A + 2, len(combined)):
        current_pi = pi[i]
        pos_in_B = i - (len_A + 1) - 1  # since combined is A + # + B
        if pos_in_B >= 0 and pos_in_B < M:
            max_k[pos_in_B] = current_pi
    
    # Initialize DP
    INF = float('inf')
    dp = [INF] * (M + 1)
    dp[0] = 0  # 0 elements
    
    for i in range(1, M + 1):
        current_max_k = max_k[i-1]  # since B is 0-based in max_k
        if current_max_k == 0:
            continue
        for k in range(1, current_max_k + 1):
            j = i - k
            if j < 0:
                continue
            if dp[j] == INF:
                continue
            cost = dp[j] + k * C[j-1]  # since C is 0-based for j=0 to M-1, and j is the length before adding k
            if cost < dp[i]:
                dp[i] = cost
    
    if dp[M] == INF:
        print(-1)
    else:
        print(dp[M])

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