提出 #61167350

---

ソースコード 拡げる

#include "bits/stdc++.h"
#include <chrono>
using namespace std;

#define LL long long
#define mod 998244353ll
//#define mod 1000000007ll
#define PI acos(-1.0)
#define set0(ar) memset(ar, 0, sizeof ar)
#define setinf(ar) memset(ar, 126, sizeof ar)

inline LL bigmod(LL p, LL e, LL M) {
  LL r = 1;
  for (; e > 0; e >>= 1, p = (p * p) % M)
    if (e & 1) r = (r * p) % M;
  return r;
}
inline LL modinverse(LL a, LL M) { return bigmod(a, M - 2, M); }

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dp[500001][41];
string S, T;

int go(int c, int k, int kmax){
  if(c+k > (int)T.size()) return kmax+1;
  if(c+k == (int)T.size()) return S.size() - c;
  if(c == (int)S.size()) {
    return (int)T.size() - (c+k);
  }
  int &ret = dp[c][k+kmax];
  if(ret != -1) return ret;
  ret = kmax+1;

  int tc = c+k;
  ret = min(ret, (S[c] != T[tc]) + go(c+1, k, kmax));
  if(k-1 >= -kmax) ret = min(ret, 1 + go(c+1, k-1, kmax));
  if(k+1 <= kmax) ret = min(ret, 1 + go(c, k+1, kmax));
  return ret;
}

void solve() {
  int k; cin >> k >> S >> T;
  memset(dp, -1, sizeof dp);
  if(go(0, 0, k) <= k) cout << "Yes\n";
  else cout << "No\n";
}


int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int T = 1;
  //cin >> T; 
  for (int ts = 1; ts <= T; ts++) {
    //cout << "Case #" << ts << ": ";
    solve();
  }
}

提出情報

ジャッジ結果