Submission #1236156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236156		overwatch9	Bajka (COCI20_bajka)	C++20	50 / 70	25 ms	840 KiB

bajka

#include <bits/stdc++.h>
using namespace std;
int n, m;
string scary, fav;
const int maxnm = 301;
int dp[maxnm][maxnm];
bool ready[maxnm][maxnm];
int solve(int i, int j) {
    if (j >= m)
        return 0;
    if (ready[i][j])
        return dp[i][j];
    int ans = 1e9;
    if (i+1 < n && scary[i+1] == fav[j])
        ans = min(ans, solve(i+1, j+1)+1);
    if (i-1 >= 0 && scary[i-1] == fav[j])
        ans = min(ans, solve(i-1, j+1)+1);
    for (int x = 0; x < n; x++) {
        if (abs(i-x) == 0)
            continue;
        if (scary[i] == scary[x]) {
            if (x-1 >= 0 && scary[x-1] == fav[j])
                ans = min(ans, solve(x-1, j+1) + abs(x - i) + 1);
            if (x+1 < n && scary[x+1] == fav[j])
                ans = min(ans, solve(x+1, j+1) + abs(x - i) + 1);
        }
    }
    ready[i][j] = true;
    dp[i][j] = ans;
    return ans;
}
int main() {
    cin >> n >> m >> scary >> fav;
    int ans = 1e9;
    for (int i = 0; i < n; i++)
        ans = min(ans, solve(i, 0));
    if (ans == 1e9)
        ans = 0;
    cout << ans-1 << '\n';
}

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