Submission #482254

#	Time	Username	Problem	Language	Result	Execution time	Memory
482254		s_samchenko	Bajka (COCI20_bajka)	C++17	70 / 70	141 ms	1012 KiB

bajka

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;

void solve(){
	int n, m;
	string s, t;
	cin >> n >> m >> s >> t;
	
	s = "." + s + "."; t = "." + t + ".";
	vector < vector <int> > dp(n+1, vector <int> (m+1, inf));
	for (int i = 1; i <= n; ++i) dp[i][0] = 0;
	for (int i = 1; i <= n; ++i)
		if (s[i] == t[1]) dp[i][1] = 0;
	for (int j = 2; j <= m; ++j)
		for (int i = 1; i <= n; ++i){
			if (dp[i][j-1] == inf) continue;
			for (int k = 1; k <= n; ++k){
				if (k == i) continue;
				if (s[k] == t[j]){
					if (abs(k - i) == 1) dp[k][j] = min(dp[k][j], dp[i][j-1] + 1);
					if (s[k-1] == t[j-1]) dp[k][j] = min(dp[k][j], dp[i][j-1] + 1 + abs(k-1 - i));
					if (s[k+1] == t[j-1]) dp[k][j] = min(dp[k][j], dp[i][j-1] + 1 + abs(k+1 - i));
				}
			}
		}
	int ans = inf;
	for (int i = 1; i <= n; ++i) ans = min(ans, dp[i][m]);
	if (ans == inf) ans = -1;
	cout << ans;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

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