제출 #1236162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236162		overwatch9	Bajka (COCI20_bajka)	C++20	0 / 70	1 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++) {
        if (i-1 >= 0 && scary[i-1] == fav[0])
            ans = min(ans, solve(i-1, 1) + 1);
        if (i+1 < n && scary[i+1] == fav[0])
            ans = min(ans, solve(i+1, 1) + 1);
    }
    if (ans == 1e9)
        ans = -1;
    cout << ans << '\n';
}

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