Submission #377624

#TimeUsernameProblemLanguageResultExecution timeMemory
377624dimashiiBajka (COCI20_bajka)C++17
20 / 70
9 ms2284 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int mxN = 1e3 + 5, mod = 1e9 + 7; const ll inf = 1e18; int n, m; ll dp[mxN][mxN]; string s, t; int main() { ios :: sync_with_stdio(false), cin.tie(nullptr); cin >> n >> m >> s >> t; for (int i = 0; i < n; ++i) { for (int j = 1; j <= m; ++j) dp[i][j] = inf; } for (int i = 0; i < n; ++i) { if (s[i] == t[0]) dp[i][1] = 0; } for (int j = 2; j <= m; ++j) { for (int i = 0; i < n; ++i) { if (s[i] == t[j - 1]) { for (int k = i - 1; k >= 0; k--) { if (s[k] == t[j - 2]) dp[i][j] = min(dp[i][j], dp[k][j - 1] + (i - k)); } for (int k = i + 1; k < n; ++k) { if (s[k] == t[j - 2]) dp[i][j] = min(dp[i][j], dp[k][j - 1] + (k - i)); } } } } ll ans = inf; for (int i = 0; i < n; ++i) ans = min(ans, dp[i][m]); if (ans == inf) ans = -1; cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...