Submission #661127

#	Time	Username	Problem	Language	Result	Execution time	Memory
661127		faik	Bajka (COCI20_bajka)	C++17	70 / 70	2 ms	980 KiB

bajka

#include "bits/stdc++.h"

using namespace std;

#define MOD 1000000007

#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int,int> pii;

ll fastpow(ll a, ll b){
	ll ret = 1;
	while(b){
		if(b%2)
			ret = ret*a%MOD;
		a = a*a%MOD;
		b >>= 1;
	}
	return ret;
}

ll dp[310][310];

void solve(){
	ll n,m;cin >> n >> m;
	string nstr;cin >> nstr;
	string mstr;cin >> mstr;

	for(int i = 0;i < n;i++){
		if(nstr[i] != mstr[0])
			dp[i][0] = INT_MAX;
	}

	for(int i = 1;i < m;i++){
		for(int j = 0;j < n;j++){
			dp[j][i] = INT_MAX;
			if(nstr[j] != mstr[i])
				continue;
			if(j != 0){
				dp[j][i] = dp[j-1][i-1]+1;
			}
			if(j != n-1){
				dp[j][i] = min(dp[j][i], dp[j+1][i-1]+1);
			}
		}
		ll current = INT_MAX;
		for(int j = 0;j < n;j++){
			current++;
			if(nstr[j] != mstr[i])
				continue;
			dp[j][i] = min(dp[j][i], current);
			current = dp[j][i];
		}
		current = INT_MAX;
		for(int j = n-1;j >= 0;j--){
			current++;
			if(nstr[j] != mstr[i])
				continue;
			dp[j][i] = min(dp[j][i], current);
			current = dp[j][i];
		}
	}
	// for(int j = 0;j < m;j++){
	// 	for(int i = 0;i < n;i++){
	// 		cout << dp[i][j] << ' ';
	// 	}
	// 	cout << '\n';
	// }
	ll ret = INT_MAX;
	for(int i = 0;i < n;i++){
		ret = min(ret,dp[i][m-1]);
	}
	if(ret == INT_MAX)
		ret = -1;
	cout << ret;
}

signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
#ifdef DEBUG
	freopen("i","r",stdin);
	freopen("o","w",stdout);
#endif
	int q = 1;
#ifdef TEST
	cin >> q;
#endif
	while(q--)
		solve();
}
//Unimaginative; 
//over-literal; 
//lacking nuance; 
//lacking in sub-text; 
//too obvious; 
//having neither subtlety nor sophistication;

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