Submission #47709230

Source Code Expand

// Author: XZC(L_Wave)
// Language: Cpp/G++14
// Problem: E - Stamp
// Contest: AtCoder - Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 329）
// URL: https://atcoder.jp/contests/abc329/tasks/abc329_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Create Time: not 2023-11-18 20:00:31, but 1926-08-17 11:45:14
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
bool dp[200010][7];
int n,m;string s,t;

int main() {
  cin>>n>>m;
  cin>>s>>t;
  s='_'+s;t='_'+t;
  dp[0][m]=1;
  rep(i,1,n)
    rep(j,1,min(i,m)){
      bool t1 = 0;
      rep(z,1,m)
        t1|=dp[i-j][z];
      t1 &= s.substr(i-j+1,j)==t.substr(1,j);
      bool t2 = 0;
      rep(z,1,j)
        t2|=dp[i-z][m]&&s.substr(i-z+1,z)==t.substr(j-z+1,z);
      dp[i][j]=t1|t2;
      //cout<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
    }
  if(dp[n][m])puts("Yes");else puts("No");
  return 0;
}

Submission Info

Submission Time
Task E - Stamp
User fft_ntt
Language C++ 20 (gcc 12.2)
Score 475
Code Size 1151 Byte
Status AC
Exec Time 61 ms
Memory 5164 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 3480 KiB
00_sample_01.txt AC 1 ms 3444 KiB
00_sample_02.txt AC 1 ms 3476 KiB
01_random_00.txt AC 7 ms 4080 KiB
01_random_01.txt AC 8 ms 4424 KiB
01_random_02.txt AC 10 ms 4676 KiB
02_random2y_00.txt AC 8 ms 4336 KiB
02_random2y_01.txt AC 14 ms 4980 KiB
02_random2y_02.txt AC 2 ms 3512 KiB
02_random2y_03.txt AC 14 ms 5028 KiB
02_random2y_04.txt AC 18 ms 4892 KiB
02_random2y_05.txt AC 19 ms 4972 KiB
02_random2y_06.txt AC 15 ms 4632 KiB
02_random2y_07.txt AC 18 ms 5028 KiB
02_random2y_08.txt AC 18 ms 4672 KiB
02_random2y_09.txt AC 25 ms 4984 KiB
02_random2y_10.txt AC 2 ms 3588 KiB
02_random2y_11.txt AC 23 ms 5020 KiB
02_random2y_12.txt AC 10 ms 4224 KiB
02_random2y_13.txt AC 29 ms 5020 KiB
02_random2y_14.txt AC 21 ms 4308 KiB
02_random2y_15.txt AC 32 ms 4956 KiB
03_random2n_00.txt AC 7 ms 4532 KiB
03_random2n_01.txt AC 14 ms 5092 KiB
03_random2n_02.txt AC 3 ms 3700 KiB
03_random2n_03.txt AC 14 ms 5164 KiB
03_random2n_04.txt AC 14 ms 4816 KiB
03_random2n_05.txt AC 17 ms 4960 KiB
03_random2n_06.txt AC 11 ms 4632 KiB
03_random2n_07.txt AC 20 ms 5020 KiB
03_random2n_08.txt AC 17 ms 4844 KiB
03_random2n_09.txt AC 20 ms 4968 KiB
03_random2n_10.txt AC 19 ms 4912 KiB
03_random2n_11.txt AC 17 ms 4976 KiB
03_random2n_12.txt AC 7 ms 4160 KiB
03_random2n_13.txt AC 26 ms 4968 KiB
03_random2n_14.txt AC 14 ms 4372 KiB
03_random2n_15.txt AC 27 ms 5032 KiB
04_killer_00.txt AC 61 ms 5028 KiB
04_killer_01.txt AC 40 ms 4980 KiB
04_killer_02.txt AC 20 ms 4932 KiB
04_killer_03.txt AC 21 ms 4936 KiB
05_handmade_00.txt AC 1 ms 3608 KiB
05_handmade_01.txt AC 1 ms 3480 KiB
05_handmade_02.txt AC 8 ms 5164 KiB
05_handmade_03.txt AC 6 ms 5020 KiB
05_handmade_04.txt AC 51 ms 5024 KiB
05_handmade_05.txt AC 1 ms 3540 KiB
05_handmade_06.txt AC 1 ms 3480 KiB
05_handmade_07.txt AC 1 ms 3540 KiB
05_handmade_08.txt AC 1 ms 3536 KiB