Submission #47754605

Source Code Expand

#ABC329E Stamp

#入力受取  Sの末尾には番兵を置いておく
N,M=map(int,input().split()); S=input(); T=input()
S+='#'

#DP[i][j]: S[i]をT[j]で塗る状態にできるか？
DP=[[False]*M for _ in range(N)]
if S[0]==T[0]: DP[0][0]=True

#DPを回す  DP[i][M-1]=True のときは、S[i+1]は(上書きされたスタンプが出てくる形で)
#T[0:j]のどれかを押せると考え遷移する
for i in range(N):
    for j in range(M):
        if DP[i][j]==False: continue
        if j <M-1:
            if S[i+1]==T[j+1]: DP[i+1][j+1]=True
        if j==M-1:  #隠し押ししていたスタンプの遷移
            for k in range(M):
                if S[i+1]==T[k]: DP[i+1][k]=True
    #DP[i]のどれかひとつでもTrueなら、i+1を起点にスタンプが押せる
    if any(DP[i]) and S[i+1]==T[0]: DP[i+1][0]=True

#Sの右端をスタンプの右端に合わせられる、すなわち S[-1]をT[-1]で押す ことができればYes
print('Yes' if DP[-1][-1] else 'No')

Submission Info

Submission Time
Task E - Stamp
User navel_tos
Language Python (PyPy 3.10-v7.3.12)
Score 475
Code Size 1030 Byte
Status AC
Exec Time 128 ms
Memory 107272 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 475 / 475
Status
AC × 3
AC × 51
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 02_random2y_00.txt, 02_random2y_01.txt, 02_random2y_02.txt, 02_random2y_03.txt, 02_random2y_04.txt, 02_random2y_05.txt, 02_random2y_06.txt, 02_random2y_07.txt, 02_random2y_08.txt, 02_random2y_09.txt, 02_random2y_10.txt, 02_random2y_11.txt, 02_random2y_12.txt, 02_random2y_13.txt, 02_random2y_14.txt, 02_random2y_15.txt, 03_random2n_00.txt, 03_random2n_01.txt, 03_random2n_02.txt, 03_random2n_03.txt, 03_random2n_04.txt, 03_random2n_05.txt, 03_random2n_06.txt, 03_random2n_07.txt, 03_random2n_08.txt, 03_random2n_09.txt, 03_random2n_10.txt, 03_random2n_11.txt, 03_random2n_12.txt, 03_random2n_13.txt, 03_random2n_14.txt, 03_random2n_15.txt, 04_killer_00.txt, 04_killer_01.txt, 04_killer_02.txt, 04_killer_03.txt, 05_handmade_00.txt, 05_handmade_01.txt, 05_handmade_02.txt, 05_handmade_03.txt, 05_handmade_04.txt, 05_handmade_05.txt, 05_handmade_06.txt, 05_handmade_07.txt, 05_handmade_08.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 58 ms 76696 KiB
00_sample_01.txt AC 58 ms 76488 KiB
00_sample_02.txt AC 58 ms 76724 KiB
01_random_00.txt AC 81 ms 89536 KiB
01_random_01.txt AC 89 ms 94452 KiB
01_random_02.txt AC 90 ms 95296 KiB
02_random2y_00.txt AC 93 ms 92412 KiB
02_random2y_01.txt AC 113 ms 102496 KiB
02_random2y_02.txt AC 73 ms 81668 KiB
02_random2y_03.txt AC 114 ms 102516 KiB
02_random2y_04.txt AC 118 ms 102780 KiB
02_random2y_05.txt AC 118 ms 104124 KiB
02_random2y_06.txt AC 111 ms 98436 KiB
02_random2y_07.txt AC 120 ms 103924 KiB
02_random2y_08.txt AC 111 ms 100884 KiB
02_random2y_09.txt AC 121 ms 105592 KiB
02_random2y_10.txt AC 73 ms 81952 KiB
02_random2y_11.txt AC 120 ms 105532 KiB
02_random2y_12.txt AC 92 ms 90584 KiB
02_random2y_13.txt AC 124 ms 107160 KiB
02_random2y_14.txt AC 100 ms 94340 KiB
02_random2y_15.txt AC 127 ms 106788 KiB
03_random2n_00.txt AC 92 ms 94544 KiB
03_random2n_01.txt AC 113 ms 102412 KiB
03_random2n_02.txt AC 75 ms 82036 KiB
03_random2n_03.txt AC 113 ms 102568 KiB
03_random2n_04.txt AC 114 ms 100768 KiB
03_random2n_05.txt AC 118 ms 103964 KiB
03_random2n_06.txt AC 103 ms 95072 KiB
03_random2n_07.txt AC 121 ms 103968 KiB
03_random2n_08.txt AC 116 ms 103112 KiB
03_random2n_09.txt AC 122 ms 105744 KiB
03_random2n_10.txt AC 119 ms 104540 KiB
03_random2n_11.txt AC 123 ms 105628 KiB
03_random2n_12.txt AC 86 ms 90528 KiB
03_random2n_13.txt AC 128 ms 106944 KiB
03_random2n_14.txt AC 100 ms 93972 KiB
03_random2n_15.txt AC 125 ms 106892 KiB
04_killer_00.txt AC 125 ms 107124 KiB
04_killer_01.txt AC 118 ms 107160 KiB
04_killer_02.txt AC 111 ms 106804 KiB
04_killer_03.txt AC 100 ms 106972 KiB
05_handmade_00.txt AC 57 ms 76356 KiB
05_handmade_01.txt AC 58 ms 76496 KiB
05_handmade_02.txt AC 70 ms 83808 KiB
05_handmade_03.txt AC 102 ms 100832 KiB
05_handmade_04.txt AC 117 ms 107272 KiB
05_handmade_05.txt AC 58 ms 76624 KiB
05_handmade_06.txt AC 58 ms 76740 KiB
05_handmade_07.txt AC 58 ms 76448 KiB
05_handmade_08.txt AC 58 ms 76764 KiB