Submission #741708

#	Time	Username	Problem	Language	Result	Execution time	Memory
741708		Alma	Bajka (COCI20_bajka)	C++17	20 / 70	1081 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) {
	if (j == m-1) return dp[i][j] = 0;
	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, 1 + solve(i-1, j+1));
	}
	if (i < n-1 && s[i+1] == t[j+1]) {
		res = min(res, 1 + solve(i+1, j+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, abs(i-k) + 1 + solve(k - 1, j + 1));
			}
			if (k < n-1 && k+1 != i && s[k+1] == t[j+1]) {
				res = min(res, abs(i-k) + 1 + solve(k+1, j+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));
		}
	}
	if (ans == 1e9) ans = -1;
	
	cout << ans << '\n';

	return 0;
}

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