Submission #468031

#	Time	Username	Problem	Language	Result	Execution time	Memory
468031		Marceantasy	Bajka (COCI20_bajka)	C++17	70 / 70	28 ms	692 KiB

bajka

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

#define ll long long; 
#define ar array; 

const int mxN = 310, M = 1e9+7; 
int n, m, dp[mxN][mxN];
string s, p;  

int solve(int a, int b){
    if(b == m) return 0; 
    if(~dp[a][b]){
        return dp[a][b];
    }
    int act = 1e9;
    for(int i = 0; i<n; ++i){
        if(s[i] == s[a]){
            if(i-1 >= 0 && s[i-1] == p[b]){
                act = min(act, solve(i-1, b+1) + abs(a-i)+1);
            }
            if(i+1 < n && s[i+1] == p[b]){
                act = min(act, solve(i+1, b+1) + abs(a-i)+1);
            }
        }
    }
    return dp[a][b] = act;
}

int main(){
    cin >> n >> m; 
    cin >> s >> p; 
    memset(dp, -1, sizeof(dp));
    int ans = 1e9; 
    for(int i = 0; i<n; ++i){
        if(s[i] == p[0]){
            ans = min(ans, solve(i, 1));
        }
    }
    if(ans >= 1e9){
        cout << -1 << "\n"; 
    }else{
        cout << ans << "\n"; 
    }
}

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