結果

問題 No.3427 Erasing a Subsequence
コンテスト
ユーザー kidodesu
提出日時 2025-12-29 17:16:46
言語 PyPy3
(7.3.17)
結果
RE  
実行時間 -
コード長 852 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 165 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 75,028 KB
最終ジャッジ日時 2026-01-11 13:04:33
合計ジャッジ時間 1,558 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n, m = map(int, input().split()); assert 1 <= m <= n <= 1000
S = list(map(int, input().split())); assert 1 <= min(S) and max(S) < 1000
T = list(map(int, input().split())); assert 1 <= min(T) and max(T) < 1000

dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n-1, -1, -1):
    for j in range(m-1, -1, -1):
        if S[i] == T[j]:
            dp[i][j] = dp[i+1][j+1]+1
        else:
            dp[i][j] = max(dp[i+1][j], dp[i][j+1])

inf = 1 << 30
Ans = [inf] * (n-m+1)
from heapq import *
hq = []
heappush(hq, (-1, inf, 0, 0))
while hq:
    k, nxt, i, j = heappop(hq)
    if Ans[k] < nxt:
        continue
    if i < n and j < m and S[i] == T[j]:
        heappush(hq, (k, nxt, i+1, j+1))
    if i < n and dp[i][j] == dp[i+1][j] and S[i] <= Ans[k+1]:
        Ans[k+1] = S[i]
        heappush(hq, (k+1, S[i], i+1, j))

print(*Ans[:-1])
0