Submission #955527

#	Time	Username	Problem	Language	Result	Execution time	Memory
955527		shezitt	Bajka (COCI20_bajka)	C++14	70 / 70	42 ms	1312 KiB

bajka

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define int ll
#define ii pair<int,int>
#define F first
#define S second
#define endl '\n'

const int N = 305;
int dp[N][N];

signed main(){
    int n, m;
    cin >> n >> m;
    string fear, fav;
    cin >> fear >> fav;

    for(int i=0; i<=m; ++i){
        for(int j=0; j<=n; ++j){
            dp[i][j] = 4e18;
        }
    }

    for(int j=0; j<n; ++j){
        if(fear[j] == fav[0]){
            dp[1][j] = 0;
        }
    }

    for(int i=1; i<m; ++i){
        for(int j=0; j<n; ++j){
            for(int k=0; k<n; ++k){
                if(fear[k] == fear[j]){
                    dp[i][k] = min(dp[i][k], dp[i][j] + abs(j - k));
                }
            }
        }
        for(int j=0; j<n; ++j){
            // left
            if(j > 0 && fear[j-1] == fav[i]){
                dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j] + 1);
            }
            // right
            if(j+1 < n && fear[j+1] == fav[i]){
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + 1);
            }
        }
    }

    int ans = 4e18;
    for(int j=0; j<n; ++j){
        ans = min(ans, dp[m][j]);
    }
    cout << (ans == 4e18 ? -1 : ans);

}

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