Submission #47705908

Source Code Expand

// Author: Ruhan Habib (ruhanhabib39@gmail.com)

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
using namespace std;

const int MAXN = 2e5;
const int MAXM = 5;

int N, M;
char S[MAXN + 10], T[MAXM + 10];
bool dp[MAXN + 10][MAXM + 1];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> N >> M >> S >> T;

    dp[N][0] = dp[N][M] = true;
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < M; j++) {
            dp[i][j] = S[i] == T[j] && dp[i+1][j+1];
            dp[i][j] = dp[i][j] || (S[i] == T[0] && dp[i+1][1]);
        }
        dp[i][M] = false;
        for (int k = 0; k < M; k++)
            dp[i][M] = dp[i][M] || (S[i] == T[k] && dp[i+1][k+1]);
    }

    cout << (dp[0][0] ? "Yes" : "No") << "\n";
}

Submission Info

Submission Time
Task E - Stamp
User ruhanhabib39
Language C++ 20 (gcc 12.2)
Score 475
Code Size 862 Byte
Status AC
Exec Time 5 ms
Memory 4936 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 1 ms 3472 KiB
00_sample_01.txt AC 1 ms 3396 KiB
00_sample_02.txt AC 1 ms 3532 KiB
01_random_00.txt AC 2 ms 3828 KiB
01_random_01.txt AC 2 ms 4312 KiB
01_random_02.txt AC 2 ms 4164 KiB
02_random2y_00.txt AC 2 ms 4296 KiB
02_random2y_01.txt AC 3 ms 4780 KiB
02_random2y_02.txt AC 1 ms 3488 KiB
02_random2y_03.txt AC 3 ms 4800 KiB
02_random2y_04.txt AC 3 ms 4592 KiB
02_random2y_05.txt AC 3 ms 4896 KiB
02_random2y_06.txt AC 3 ms 4484 KiB
02_random2y_07.txt AC 3 ms 4888 KiB
02_random2y_08.txt AC 4 ms 4396 KiB
02_random2y_09.txt AC 4 ms 4756 KiB
02_random2y_10.txt AC 1 ms 3460 KiB
02_random2y_11.txt AC 4 ms 4776 KiB
02_random2y_12.txt AC 2 ms 3784 KiB
02_random2y_13.txt AC 5 ms 4936 KiB
02_random2y_14.txt AC 3 ms 4180 KiB
02_random2y_15.txt AC 4 ms 4816 KiB
03_random2n_00.txt AC 2 ms 4336 KiB
03_random2n_01.txt AC 3 ms 4888 KiB
03_random2n_02.txt AC 1 ms 3452 KiB
03_random2n_03.txt AC 3 ms 4788 KiB
03_random2n_04.txt AC 3 ms 4596 KiB
03_random2n_05.txt AC 4 ms 4760 KiB
03_random2n_06.txt AC 2 ms 4132 KiB
03_random2n_07.txt AC 4 ms 4764 KiB
03_random2n_08.txt AC 4 ms 4636 KiB
03_random2n_09.txt AC 4 ms 4776 KiB
03_random2n_10.txt AC 4 ms 4772 KiB
03_random2n_11.txt AC 4 ms 4748 KiB
03_random2n_12.txt AC 2 ms 3908 KiB
03_random2n_13.txt AC 4 ms 4760 KiB
03_random2n_14.txt AC 3 ms 4044 KiB
03_random2n_15.txt AC 4 ms 4756 KiB
04_killer_00.txt AC 3 ms 4884 KiB
04_killer_01.txt AC 3 ms 4756 KiB
04_killer_02.txt AC 3 ms 4800 KiB
04_killer_03.txt AC 3 ms 4828 KiB
05_handmade_00.txt AC 1 ms 3468 KiB
05_handmade_01.txt AC 1 ms 3336 KiB
05_handmade_02.txt AC 2 ms 4828 KiB
05_handmade_03.txt AC 2 ms 4784 KiB
05_handmade_04.txt AC 3 ms 4768 KiB
05_handmade_05.txt AC 1 ms 3364 KiB
05_handmade_06.txt AC 2 ms 3520 KiB
05_handmade_07.txt AC 1 ms 3404 KiB
05_handmade_08.txt AC 1 ms 3332 KiB