제출 #1164904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164904		kerem	Bajka (COCI20_bajka)	C++20	70 / 70	17 ms	1096 KiB

bajka

#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e9
#define N 1000000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

int n,m,dp[300][300][2];
vector<int> v[26];
string s,t;

int ff(int i,int j,int k){
	if(j==m) return 0;
	if(dp[i][j][k]!=inf+1) return dp[i][j][k];
	dp[i][j][k]=inf;
	if(i!=0 && s[i-1]==t[j])
		dp[i][j][k]=min(dp[i][j][k],ff(i-1,j+1,1)+1);
	if(i!=n-1 && s[i+1]==t[j])
		dp[i][j][k]=min(dp[i][j][k],ff(i+1,j+1,1)+1);
	if(k){
		for(auto it:v[s[i]-'a'])
			dp[i][j][k]=min(dp[i][j][k],ff(it,j,0)+abs(i-it));
	}
	return dp[i][j][k];
}

void solve(){
	cin >> n >> m;
	cin >> s >> t;
	for(int i=0;i<n;i++)
		v[s[i]-'a'].pb(i);
		
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			dp[i][j][0]=dp[i][j][1]=inf+1;
	int ans=inf;
	for(auto i:v[t[0]-'a'])
		ans=min(ans,ff(i,1,0));
	if(ans==inf) cout << -1 << endl;
	else cout << ans << endl;
}
int32_t main(){
	//~ freopen("a.txt","r",stdin);
	//~ freopen("a.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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