oj.uz

답안 #445814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445814 2021-07-19T16:41:43 Z Jasiekstrz Bajka (COCI20_bajka) C++17
70 / 70
 99 ms 684 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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