Submission #333873

#TimeUsernameProblemLanguageResultExecution timeMemory
333873wiwihoBajka (COCI20_bajka)C++14
0 / 70
1 ms1004 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define mp make_pair #define F first #define S second #define iter(a) a.begin(), a.end() using namespace std; typedef long long ll; const ll MAX = 2147483647; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; string a, b; cin >> a >> b; vector<vector<ll>> dp(m, vector<ll>(n, MAX)); for(int i = 0; i < n; i++){ if(a[i] == b[0]) dp[0][i] = 0; } for(int i = 0; i < m - 1; i++){ for(int j = 0; j < n; j++){ if(dp[i][j] == MAX) continue; if(j && a[j - 1] == b[i + 1]) dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j] + 1); if(j < n - 1 && a[j + 1] == b[i + 1]) dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j] + 1); for(int k = 0; k < n; k++){ if(a[k] == b[i]) dp[i][k] = min(dp[i][k], dp[i][j] + abs(j - k)); } } } int ans = *min_element(iter(dp[m - 1])); if(ans == MAX) ans = -1; cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...