結果

問題 No.2332 Make a Sequence
ユーザー lam6er
提出日時 2025-04-16 16:04:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,330 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 82,016 KB
実行使用メモリ 133,176 KB
最終ジャッジ日時 2025-04-16 16:11:09
合計ジャッジ時間 25,424 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from heapq import heappush, heappop

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 + 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
    
    l_max = [0] * M
    for j in range(M):
        pos = N + j
        max_len = Z[pos] if pos < n else 0
        max_len = min(max_len, N)
        max_len = min(max_len, M - j)
        l_max[j] = max_len
    
    INF = 1 << 60
    dp = [INF] * (M + 1)
    dp[0] = 0
    
    events = []
    for j in range(M):
        if l_max[j] == 0:
            continue
        start = j + 1
        end = j + l_max[j]
        if start > M:
            continue
        if end > M:
            end = M
        heappush(events, (start, j, 'add'))
        heappush(events, (end + 1, j, 'remove'))
    
    active = {}
    line_dict = {}
    
    for i in range(1, M + 1):
        while events and events[0][0] <= i:
            t, j, typ = heappop(events)
            if typ == 'add':
                if dp[j] == INF:
                    continue
                c = C[j]
                d = dp[j] - j * c
                active[j] = (c, d)
            else:
                if j in active:
                    del active[j]
        
        min_val = INF
        for j in active:
            c, d = active[j]
            val = c * i + d
            if val < min_val:
                min_val = val
        if min_val != INF:
            dp[i] = min_val
        
        if i < M and dp[i] != INF and l_max[i] > 0:
            start = i + 1
            end = i + l_max[i]
            if start > M:
                continue
            if end > M:
                end = M
            heappush(events, (start, i, 'add'))
            heappush(events, (end + 1, i, 'remove'))
    
    print(dp[M] if dp[M] != INF else -1)

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