Submission #1138322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138322		_rain_	Bajka (COCI20_bajka)	C++20	70 / 70	26 ms	584 KiB

bajka

// Source: https://usaco.guide/general/io

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)

const int N=302;
int dp[N+2][N+2];
int n,m;
string s1,s2;

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin>>n>>m;
	cin>>s1>>s2; s1='#'+s1,s2='#'+s2;
	memset(dp,0x3f,sizeof dp);
	FOR(i,1,n) if (s1[i]==s2[1]) dp[1][i]=0;
	int INF=dp[0][0];
	FOR(i,2,m){
		FOR(j1,1,n){
			if (s1[j1]==s2[i]) dp[i][j1]=min(dp[i-1][j1-1]+1,dp[i][j1]);
			if (s1[j1]==s2[i]) dp[i][j1]=min(dp[i-1][j1+1]+1,dp[i][j1]);
		}
		FOR(j1,1,n) FOR(j2,1,n){
			if (s1[j1]==s1[j2]) dp[i][j2]=min(dp[i][j2],dp[i][j1]+abs(j1-j2));
		}
	}
	int ans=INF;
	FOR(i,1,n) ans=min(ans,dp[m][i]);
	cout<<(ans==INF?-1:ans);
}

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