Submission #47724162

Source Code Expand

#![allow(dead_code)]

use proconio::marker::Chars;
fn main() {
    proconio::input! {
        n: usize,
        m: usize,
        s: Chars,
        t: Chars
    }
    let mut dp = vec![vec![vec![0; 1 << m]; m]; n + 1];
    dp[0][0][0] = 1;
    for i in 0..=(n - m) {
        for j2 in 0..m {
            for j in 0..(1usize << m) {
                if dp[i][j2][j] == 0 {
                    continue;
                }
                if j & 1 == 0 {
                    // かならず上におす
                    if s[i] != t[0] {
                        continue;
                    }
                    let mut nj = 0;
                    for k in 0..m {
                        if s[i + k] == t[k] {
                            nj += 1 << k;
                        }
                    }
                    dp[i + 1][m - 1][nj >> 1] = 1;
                } else {
                    if s[i] == t[0] {
                        let mut nj = 0;
                        for k in 0..m {
                            if s[i + k] == t[k] {
                                nj += 1 << k;
                            }
                        }
                        dp[i + 1][m - 1][nj >> 1] = 1;
                    }
                    // 下に押す
                    {
                        let mut nj = j >> 1;
                        for k in j2..m {
                            if s[i + k] == t[k] {
                                nj |= 1 << k;
                            } else {
                                nj &= !(1 << k);
                            }
                        }
                        dp[i + 1][m - 1][nj >> 1] = 1;
                    }

                    dp[i + 1][j2.saturating_sub(1)][j >> 1] = 1;
                }
            }
        }
    }
    for q in 0..m {
        if dp[n - m + 1][q][(1 << (m - 1)) - 1] > 0 {
            println!("Yes");
            return;
        }
    }
    println!("No");
}

Submission Info

Submission Time
Task E - Stamp
User Lenqth
Language Rust (rustc 1.70.0)
Score 0
Code Size 1958 Byte
Status WA
Exec Time 165 ms
Memory 173124 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 475
Status
AC × 3
AC × 35
WA × 16
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 1920 KiB
00_sample_01.txt AC 1 ms 2068 KiB
00_sample_02.txt AC 1 ms 1976 KiB
01_random_00.txt AC 45 ms 53704 KiB
01_random_01.txt AC 26 ms 30104 KiB
01_random_02.txt AC 43 ms 52484 KiB
02_random2y_00.txt AC 16 ms 17092 KiB
02_random2y_01.txt AC 30 ms 32464 KiB
02_random2y_02.txt AC 2 ms 3120 KiB
02_random2y_03.txt AC 30 ms 32192 KiB
02_random2y_04.txt WA 42 ms 47872 KiB
02_random2y_05.txt WA 45 ms 51172 KiB
02_random2y_06.txt WA 34 ms 38352 KiB
02_random2y_07.txt WA 45 ms 51220 KiB
02_random2y_08.txt WA 60 ms 72160 KiB
02_random2y_09.txt WA 75 ms 91800 KiB
02_random2y_10.txt WA 5 ms 6536 KiB
02_random2y_11.txt WA 75 ms 91660 KiB
02_random2y_12.txt WA 52 ms 57956 KiB
02_random2y_13.txt WA 143 ms 173088 KiB
02_random2y_14.txt WA 70 ms 83328 KiB
02_random2y_15.txt WA 143 ms 173112 KiB
03_random2n_00.txt AC 18 ms 21388 KiB
03_random2n_01.txt AC 30 ms 32356 KiB
03_random2n_02.txt AC 4 ms 4436 KiB
03_random2n_03.txt AC 30 ms 32416 KiB
03_random2n_04.txt AC 38 ms 43312 KiB
03_random2n_05.txt AC 44 ms 51144 KiB
03_random2n_06.txt AC 27 ms 30328 KiB
03_random2n_07.txt AC 46 ms 51012 KiB
03_random2n_08.txt AC 68 ms 82788 KiB
03_random2n_09.txt AC 76 ms 91872 KiB
03_random2n_10.txt AC 73 ms 87536 KiB
03_random2n_11.txt WA 80 ms 91644 KiB
03_random2n_12.txt AC 52 ms 56808 KiB
03_random2n_13.txt AC 143 ms 173116 KiB
03_random2n_14.txt AC 68 ms 80388 KiB
03_random2n_15.txt AC 143 ms 173124 KiB
04_killer_00.txt WA 143 ms 173048 KiB
04_killer_01.txt WA 146 ms 173096 KiB
04_killer_02.txt AC 143 ms 173100 KiB
04_killer_03.txt AC 147 ms 173112 KiB
05_handmade_00.txt AC 1 ms 1792 KiB
05_handmade_01.txt AC 1 ms 2004 KiB
05_handmade_02.txt AC 18 ms 20068 KiB
05_handmade_03.txt AC 17 ms 20028 KiB
05_handmade_04.txt AC 165 ms 173072 KiB
05_handmade_05.txt AC 1 ms 2008 KiB
05_handmade_06.txt WA 1 ms 1852 KiB
05_handmade_07.txt AC 1 ms 2004 KiB
05_handmade_08.txt AC 1 ms 1908 KiB