This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=305,mod=1e9+7,Inf=1e15;
int dp[N][N],m,n;
string s,t;
main(){
// t=1;
cin >> n >> m;
cin >> s;
s='#'+s;
cin >> t;
t='#'+t;
for(int i=1;i<=m;i++) {
for(int j=0;j<=n+1;j++) {
dp[i][j] = Inf;
}
}
int ans = Inf;
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++){
if(s[j]==t[i]) {
dp[i][j] = min(dp[i][j], min(dp[i-1][j-1],dp[i-1][j+1])+1);
if(i==1) dp[i][j] = 0;
for(int k=1;k<=n;k++){
if(s[j]==s[k])dp[i][k] = min(dp[i][k],dp[i][j] + abs(j-k));
}
}
}
if(i==m)
for(int j=1;j<=n;j++){
ans = min(ans,dp[i][j]);
}
}
if(ans==Inf) cout<<-1;
else cout<<ans;
}
Compilation message (stderr)
bajka.cpp:9:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
9 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |