Submission #445814

#	Time	Username	Problem	Language	Result	Execution time	Memory
445814		Jasiekstrz	Bajka (COCI20_bajka)	C++17	70 / 70	99 ms	684 KiB

bajka

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int INF=1e9+7;
const int N=300;
int dp[N+10][N+10];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	string s,t;
	cin>>s>>t;
	for(int i=0;i<=n+1;i++)
		dp[0][i]=-1;
	for(int j=1;j<=m;j++)
	{
		dp[j][0]=dp[j][n+1]=INF;
		for(int i=1;i<=n;i++)
		{
			dp[j][i]=INF;
			if(s[i-1]==t[j-1])
				dp[j][i]=min(dp[j-1][i-1],dp[j-1][i+1])+1;
		}
		for(int i=1;i<=n;i++)
		{
			for(int k=1;k<=n;k++)
			{
				if(s[i-1]==s[k-1])
					dp[j][i]=min(dp[j][i],dp[j][k]+abs(k-i));
			}
		}
	}
	int ans=INF;
	for(int i=1;i<=n;i++)
		ans=min(ans,dp[m][i]);
	cout<<(ans==INF ? -1:ans)<<"\n";
	return 0;
}

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