제출 #482254

#제출 시각아이디문제언어결과실행 시간메모리
482254s_samchenkoBajka (COCI20_bajka)C++17
70 / 70
141 ms1012 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target ("avx2") #define ll long long #define ff first #define ss second #define int ll #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define pb push_back #define pii pair <int, int> using namespace std; const int inf = 1e15; const int mod = 1e9+7; const int N = 2e5+100; void solve(){ int n, m; string s, t; cin >> n >> m >> s >> t; s = "." + s + "."; t = "." + t + "."; vector < vector <int> > dp(n+1, vector <int> (m+1, inf)); for (int i = 1; i <= n; ++i) dp[i][0] = 0; for (int i = 1; i <= n; ++i) if (s[i] == t[1]) dp[i][1] = 0; for (int j = 2; j <= m; ++j) for (int i = 1; i <= n; ++i){ if (dp[i][j-1] == inf) continue; for (int k = 1; k <= n; ++k){ if (k == i) continue; if (s[k] == t[j]){ if (abs(k - i) == 1) dp[k][j] = min(dp[k][j], dp[i][j-1] + 1); if (s[k-1] == t[j-1]) dp[k][j] = min(dp[k][j], dp[i][j-1] + 1 + abs(k-1 - i)); if (s[k+1] == t[j-1]) dp[k][j] = min(dp[k][j], dp[i][j-1] + 1 + abs(k+1 - i)); } } } int ans = inf; for (int i = 1; i <= n; ++i) ans = min(ans, dp[i][m]); if (ans == inf) ans = -1; cout << ans; } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int tt = 1; //cin >> tt; while (tt--){ solve(); cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...