Submission #1166510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166510		thinknoexit	Bajka (COCI20_bajka)	C++20	70 / 70	1 ms	584 KiB

bajka

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
string a, b;
int dp[303][303];
int mn[26];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    memset(dp, 0x3f, sizeof dp);
    int n, m;
    cin >> n >> m;
    cin >> a; a = " " + a;
    cin >> b; b = " " + b;
    for (int i = 1;i <= n;i++) {
        if (a[i] == b[1]) dp[1][i] = 0;
    }
    for (int i = 2;i <= m;i++) {
        memset(mn, 0x3f, sizeof mn);
        for (int j = 1;j <= n;j++) {
            dp[i - 1][j] = min(dp[i - 1][j], mn[a[j] - 'a'] + j);
            mn[a[j] - 'a'] = min(mn[a[j] - 'a'], dp[i - 1][j] - j);
        }
        memset(mn, 0x3f, sizeof mn);
        for (int j = n;j >= 1;j--) {
            dp[i - 1][j] = min(dp[i - 1][j], mn[a[j] - 'a'] - j);
            mn[a[j] - 'a'] = min(mn[a[j] - 'a'], dp[i - 1][j] + j);
        }
        // transition
        for (int j = 1;j <= n;j++) {
            if (a[j] != b[i]) continue;
            if (j != 1) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
            if (j != n) dp[i][j] = min(dp[i][j], dp[i - 1][j + 1] + 1);
        }
    }
    int ans = *min_element(dp[m] + 1, dp[m] + 1 + n);
    if (ans >= 1e9) cout << "-1\n";
    else cout << ans << '\n';
    return 0;
}

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