Submission #705779

#TimeUsernameProblemLanguageResultExecution timeMemory
705779AbitoBajka (COCI20_bajka)C++17
50 / 70
48 ms1268 KiB
#include <bits/stdc++.h> #define F first #define S second #define pb push_back #define ppb pop_back #define ep insert #define endl '\n' #define elif else if #define pow pwr #define sqrt sqrtt #define int long long typedef unsigned long long ull; using namespace std; const int N=305; int dp[N][N],n,m; char a[N],b[N]; bool vis[N][N]; vector<int> adj[30]; int rec(int i,int j){ //cout<<i<<' '<<j<<endl; if (j==m) return 0; if (vis[i][j]) return dp[i][j]; vis[i][j]=true; dp[i][j]=INT_MAX; if (i>1){ if (a[i-1]==b[j+1]) dp[i][j]=min(dp[i][j],rec(i-1,j+1)+1); } if (i<n){ if (a[i+1]==b[j+1]) dp[i][j]=min(dp[i][j],rec(i+1,j+1)+1); } for (auto u:adj[a[i]-'a']) dp[i][j]=min(dp[i][j],rec(u,j)+abs(u-i)); return dp[i][j]; } int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin>>n>>m; for (int i=1;i<=n;i++){ cin>>a[i]; adj[a[i]-'a'].pb(i); } for (int j=1;j<=m;j++) cin>>b[j]; int ans=INT_MAX; for (int i=1;i<=n;i++) ans=min(ans,rec(i,0)); if (ans>=INT_MAX) cout<<-1<<endl; else cout<<ans-1<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...