Submission #674935

#	Time	Username	Problem	Language	Result	Execution time	Memory
674935		vjudge1	Bajka (COCI20_bajka)	C++17	20 / 70	1 ms	596 KiB

bajka

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define endl "\n"
 
const int MOD = 998244353;

void solve(){
	int n, m; cin >> n >> m;
	string s; cin >> s; 
	string t; cin >> t;
	vector<vector<int>> dp(m, vector<int>(n, -1));
	for(int i = 0; i < n; i++){
		if(s[i] == t[0]) dp[0][i] = 0;
	}
	for(int i = 1; i < m; i++){
		for(int j = 0; j < n; j++){
			if(dp[i - 1][j] == -1) continue;
			for(int q = 0; q < n; q++){
				if(q == j) continue;
				if(s[q] == t[i]){
					if(q == j + 1 || q == j - 1){
						if(dp[i][q] == -1) dp[i][q] = dp[i - 1][j] + 1;
						else dp[i][q] = min(dp[i][q], dp[i - 1][j] + 1);
					}else if(q + 1 < n && s[q + 1] == s[j]){
						int cost = dp[i - 1][j] + abs(q + 1 - j) + 1;
						if(dp[i][q] == -1) dp[i][q] = cost;
						else dp[i][q] = min(dp[i][q], cost);
					}else if(q - 1 < n && s[q - 1] == s[j]){
						int cost = dp[i - 1][j] + abs(q - 1 - j) + 1;
						if(dp[i][q] == -1) dp[i][q] = cost;
						else dp[i][q] = min(dp[i][q], cost);
					}
				}
			}
		}
		//~ for(int j = 0; j < n; j++){
			//~ if(dp[i][j] == -1) continue;
			//~ for(int q = 0; q < n; q++){
				//~ if(dp[i][q] == -1) dp[i][q] = dp[i][j] + abs(q - j);
				//~ else dp[i][q] = min(dp[i][q], dp[i][j] + abs(q - j));
			//~ }
		//~ }
	}
	int ans = -1;
	for(int i = 0; i < n; i++){
		if(dp[m - 1][i] != -1){
			if(ans == -1) ans = dp[m - 1][i];
			else ans = min(ans, dp[m - 1][i]);
		}
	}
	cout << ans << endl;
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    //int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

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