Submission #741705

#	Time	Username	Problem	Language	Result	Execution time	Memory
741705		Alma	Bajka (COCI20_bajka)	C++17	0 / 70	1071 ms	596 KiB

bajka

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
string s, t;
vector<vector<int>> dp;

int solve(int i, int j, int cost) {
	if (j == m-1) return dp[i][j] = cost;
	// if (dp[i][j] != 1e9) return dp[i][j];

	int res = 1e9;
	
	// adjacent
	if (i > 0 && s[i-1] == t[j+1]) {
		res = min(res, solve(i-1, j+1, cost+1));
	}
	if (i < n-1 && s[i+1] == t[j+1]) {
		res = min(res, solve(i+1, j+1, cost+1));	
	}

	// same letter jump
	for (int k = 0; k < n; k++) {
		if (s[i] == s[k]) {
			if (k > 0 && k-1 != i && s[k-1] == t[j+1]) {
				res = min(res, solve(k-1, j+1, cost + abs(i-k) + 1));
			}
			if (k < n-1 && k+1 != i && s[k+1] == t[j+1]) {
				res = min(res, solve(k+1, j+1, cost + abs(i-k) + 1));
			}
		}
	}

	return dp[i][j] = res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m >> s >> t;
	dp = vector<vector<int>>(n, vector<int>(m, 1e9));

	int ans = 1e9;
	for (int i = 0; i < n; i++) {
		if (s[i] == t[0]) {
			ans = min(ans, solve(i, 0, 0));
		}
	}
	if (ans == 1e9) ans = -1;
	
	cout << ans << '\n';

	return 0;
}

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