Submission #1236058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236058		toast12	Bajka (COCI20_bajka)	C++20	70 / 70	16 ms	584 KiB

bajka

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    s = '.'+s;
    t = '.'+t;
    vector<vector<int>> dp(m+1, vector<int>(n+2, INF));
    fill(dp[0].begin(), dp[0].end(), 0);
    int ans = INF;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (t[i] == s[j]) {
                dp[i][j] = min({dp[i][j], dp[i-1][j-1]+1, dp[i-1][j+1]+1});
                if (i == 1) dp[i][j] = 0;
                for (int k = 1; k <= n; k++) {
                    if (s[j] == s[k]) dp[i][k] = min(dp[i][k], dp[i][j]+abs(j-k));
                }
            }
        }
        if (i == m) {
            for (int j = 1; j <= n; j++) {
                if (s[j] == t[i]) ans = min(ans, dp[i][j]);
            }
        }
    }
    if (ans == INF) ans = -1;
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50