Submission #445813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
445813	2021-07-19T16:39:20 Z	Jasiekstrz	Bajka (COCI20_bajka)	C++17	50 / 70	101 ms	656 KB

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=1;i<=n;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

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	596 KB	Output is correct
2	Correct	51 ms	640 KB	Output is correct
3	Correct	42 ms	588 KB	Output is correct
4	Correct	44 ms	568 KB	Output is correct
5	Correct	3 ms	332 KB	Output is correct
6	Correct	4 ms	332 KB	Output is correct
7	Correct	68 ms	656 KB	Output is correct
8	Correct	56 ms	560 KB	Output is correct
9	Correct	101 ms	632 KB	Output is correct
10	Correct	2 ms	204 KB	Output is correct
11	Correct	66 ms	604 KB	Output is correct