Submission #1020441

#TimeUsernameProblemLanguageResultExecution timeMemory
1020441vjudge1Bajka (COCI20_bajka)C++17
70 / 70
62 ms856 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=305;
int const inf=1e9+7;

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

int main(){
	cin>>n>>m>>s>>t;
	for(int j=1;j<m;j++)
		for(int i=0;i<n;i++){
			dp[i][j]=inf;
			for(int k=0;k<n;k++){
				if(s[k]!=s[i])continue;
				if(k>0 && s[k-1]==t[m-j])
					dp[i][j]=min(dp[i][j],abs(i-k)+1+dp[k-1][j-1]);
				if(k+1<n && s[k+1]==t[m-j])
					dp[i][j]=min(dp[i][j],abs(i-k)+1+dp[k+1][j-1]);
			}
		}
	int ans=inf;
	for(int i=0;i<n;i++)
		if(s[i]==t[0])
			ans=min(ans,dp[i][m-1]);
	if(ans==inf)
		ans=-1;
	cout<<ans<<endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...