Submission #674934

#TimeUsernameProblemLanguageResultExecution timeMemory
674934vjudge1Bajka (COCI20_bajka)C++17
0 / 70
81 ms596 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" const int MOD = 998244353; void solve(){ int n, m; cin >> n >> m; string s; cin >> s; string t; cin >> t; vector<vector<int>> dp(m, vector<int>(n, -1)); for(int i = 0; i < n; i++){ if(s[i] == t[0]) dp[0][i] = 0; } for(int i = 1; i < m; i++){ for(int j = 0; j < n; j++){ if(dp[i - 1][j] == -1) continue; for(int q = 0; q < n; q++){ if(q == j) continue; if(s[q] == t[i]){ if(q == j + 1 || q == j - 1){ if(dp[i][q] == -1) dp[i][q] = dp[i - 1][j] + 1; else dp[i][q] = min(dp[i][q], dp[i - 1][j] + 1); }else if(q + 1 < n && s[q + 1] == s[j]){ int cost = dp[i - 1][j] + abs(q + 1 - j) + 1; if(dp[i][q] == -1) dp[i][q] = cost; else dp[i][q] = min(dp[i][q], cost); }else if(q - 1 < n && s[q - 1] == s[j]){ int cost = dp[i - 1][j] + abs(q - 1 - j) + 1; if(dp[i][q] == -1) dp[i][q] = cost; else dp[i][q] = min(dp[i][q], cost); } } } } for(int j = 0; j < n; j++){ if(dp[i][j] == -1) continue; for(int q = 0; q < n; q++){ if(dp[i][q] == -1) dp[i][q] = dp[i][j] + abs(q - j); else dp[i][q] = min(dp[i][q], dp[i][j] + abs(q - j)); } } } int ans = -1; for(int i = 0; i < n; i++){ if(dp[m - 1][i] != -1){ if(ans == -1) ans = dp[m - 1][i]; else ans = min(ans, dp[m - 1][i]); } } cout << ans << endl; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("inpt.txt", "r", stdin); //freopen("out.txt", "w", stdout); //int tt; cin >> tt; int tt = 1; for(int t = 1; t <= tt; t++){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...