제출 #1333422

#제출 시각아이디문제언어결과실행 시간메모리
1333422ahmetlbktd4Bajka (COCI20_bajka)C++20
70 / 70
52 ms788 KiB
#include "bits/stdc++.h"
using namespace std;

const int N = 301;
const int inf = 1e9;

int n,m,dp[N][N];
string s,s1;

int coz(int a,int b){
    if (b == m)
    return 0;
    int &h = dp[a][b];
    if (~h)
    return h;
    h = inf;
    for (int i = 0;i < n;i++){
        if (s[i] == s[a]){
            for (int j = -1;j < 2;j++){
                if (!j || i+j<0 || i+j>= n)
                continue;
                if (s[i+j] ^ s1[b])
                continue;
                h = min(h,coz(i+j,b+1) + abs(i-a)+1); 
            }
        }
    }
    return h;
}

int main(){
    cin >> n >> m;
    cin >> s;
    cin >> s1;
    memset(dp,-1,sizeof dp);
    int p = inf;
    for (int i = 0;i < n;i++){
        if (s[i] == s1[0])
        p = min(p,coz(i,1));
    }
    if (p >= inf)
    p = -1;
    cout << p << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...