oj.uz

Submission #741708

# Submission time Handle Problem Language Result Execution time Memory
741708 2023-05-14T16:00:49 Z Alma Bajka (COCI20_bajka) C++17
20 / 70
 1000 ms 596 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -