oj.uz

Submission #1020441

# Submission time Handle Problem Language Result Execution time Memory
1020441 2024-07-12T04:32:37 Z vjudge1 Bajka (COCI20_bajka) C++17
70 / 70
 62 ms 856 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=305;
int const inf=1e9+7;

int n,m;
string s,t;
int dp[N][N];

int main(){
	cin>>n>>m>>s>>t;
	for(int j=1;j<m;j++)
		for(int i=0;i<n;i++){
			dp[i][j]=inf;
			for(int k=0;k<n;k++){
				if(s[k]!=s[i])continue;
				if(k>0 && s[k-1]==t[m-j])
					dp[i][j]=min(dp[i][j],abs(i-k)+1+dp[k-1][j-1]);
				if(k+1<n && s[k+1]==t[m-j])
					dp[i][j]=min(dp[i][j],abs(i-k)+1+dp[k+1][j-1]);
			}
		}
	int ans=inf;
	for(int i=0;i<n;i++)
		if(s[i]==t[0])
			ans=min(ans,dp[i][m-1]);
	if(ans==inf)
		ans=-1;
	cout<<ans<<endl;
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 604 KB Output is correct
2 Correct 33 ms 600 KB Output is correct
3 Correct 25 ms 600 KB Output is correct
4 Correct 26 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 36 ms 604 KB Output is correct
8 Correct 46 ms 604 KB Output is correct
9 Correct 62 ms 604 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 33 ms 604 KB Output is correct