Submission #447825

#TimeUsernameProblemLanguageResultExecution timeMemory
447825ApiramBajka (COCI20_bajka)C++14
0 / 70
3 ms972 KiB
#include<bits/stdc++.h> using namespace std; vector<vector<int>>freq(26); int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m;cin>>n>>m; string s; cin>>s; string t;cin>>t; for (int i = 0 ;i<n;++i){ freq[s[i]-'a'].push_back(i); } vector<vector<int64_t>>dp(m+1,vector<int64_t>(n+1,INT_MAX)); for (int i = 0;i<=n;++i){ dp[0][i]=0; } for (int i = 1;i<=m;++i){ for (int j = 1;j<=n;++j){ if (s[j-1]==t[i-1]){ 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 (auto x:freq[t[i-1]-'a']){ dp[i][x]=min(dp[i][j]+abs(j-x),dp[i][x]); dp[i][x]=min(dp[i][j]+abs(j-x),dp[i][x]); } } } } for (int i = 0;i<=n;++i){ dp[m][0]=min(dp[m][i],dp[m][0]); } cout<<dp[m][0]; return 0;}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...