結果

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

ソースコード

diff # 

import sys
from collections import deque

def compute_z(s):
    n = len(s)
    Z = [0] * n
    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
    return Z

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, M = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    A = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    B = list(map(int, input[ptr:ptr+M]))
    ptr +=M
    C = list(map(int, input[ptr:ptr+M]))
    ptr +=M
    
    S = A + B
    Z = compute_z(S)
    len_A = N
    max_k = [0] * M
    for j in range(M):
        pos_in_S = len_A + j
        z_val = Z[pos_in_S] if pos_in_S < len(S) else 0
        mk = min(z_val, N, M - j)
        max_k[j] = mk
    
    INF = float('inf')
    dp = [INF] * (M + 1)
    dp[0] = 0
    
    dq = deque()
    
    for j in range(M):
        if dp[j] == INF:
            continue
        mk = max_k[j]
        if mk < 1:
            continue
        c = C[j]
        intercept = dp[j] - j * c
        expire = j + mk + 1
        
        while dq and dq[0][0] <= j:
            dq.popleft()
        
        new_line = (c, intercept, expire)
        while dq:
            prev_expire = dq[-1][2]
            if prev_expire <= j + 1:
                dq.pop()
            else:
                break
        
        while len(dq) >= 2:
            c1, i1, e1 = dq[-2]
            c2, i2, e2 = dq[-1]
            x = j + 1
            val1 = c1 * x + i1
            val2 = c2 * x + i2
            val_new = new_line[0] * x + new_line[1]
            if val_new <= val2:
                dq.pop()
            else:
                break
        dq.append(new_line)
        
        while dq and dq[0][2] <= j + 1:
            dq.popleft()
        
        if dq:
            best_c, best_i, _ = dq[0]
            dp[j + 1] = best_c * (j + 1) + best_i
    
    for j in range(M):
        if dp[j] == INF:
            continue
        mk = max_k[j]
        if mk < 1:
            continue
        for k in range(1, mk + 1):
            if j + k > M:
                break
            cost = dp[j] + k * C[j]
            if cost < dp[j + k]:
                dp[j + k] = cost
    
    if dp[M] == INF:
        print(-1)
    else:
        print(dp[M])

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