Submission #445814

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
445814	2021-07-19T16:41:43 Z	Jasiekstrz	Bajka (COCI20_bajka)	C++17	70 / 70	99 ms	684 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=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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	588 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	588 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	1 ms	572 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	580 KB	Output is correct
2	Correct	51 ms	608 KB	Output is correct
3	Correct	44 ms	656 KB	Output is correct
4	Correct	43 ms	536 KB	Output is correct
5	Correct	3 ms	332 KB	Output is correct
6	Correct	3 ms	332 KB	Output is correct
7	Correct	67 ms	604 KB	Output is correct
8	Correct	56 ms	564 KB	Output is correct
9	Correct	99 ms	652 KB	Output is correct
10	Correct	2 ms	204 KB	Output is correct
11	Correct	66 ms	684 KB	Output is correct