Submission #741724

#	Time	Username	Problem	Language	Result	Execution time	Memory
741724		a_aguilo	Bajka (COCI20_bajka)	C++14	20 / 70	6 ms	620 KiB

bajka

#include<bits/stdc++.h>

using namespace std;

int n, m;
string workOn, goal;

int main(){
	cin >> n >> m;
	cin >> workOn >> goal;
	if(m == 1){
		bool exists = false;
		for(int i = 0; i < n; ++i){
			if(workOn[i] == goal[0]) exists = true;
		}
		if(exists) cout << 0 << endl;
		else cout << -1 << endl;
		return 0;
	}
	vector<vector<int>> dp(m-1, vector<int>(n, 1e9));
	for(int i = 0; i < n; ++i){
		if(workOn[i] == goal[0]){
			if(i){
				if(workOn[i-1] == goal[1]){
					dp[0][i-1] = 1;
				}
			}
			if(i <(n-1)){
				if(workOn[i+1] == goal[1]){
					dp[0][i+1] = 1;
				}
			}
		}
	}
	for(int letterNum = 1; letterNum < m-1; ++letterNum){
		for(int actualPosition = 0; actualPosition < n; ++actualPosition){
			if(workOn[actualPosition] != goal[letterNum]) continue;

			int bestPrev = 1e9;
			for(int prevPosition = 0; prevPosition < n; ++prevPosition){
				if(dp[letterNum-1][prevPosition] == 1e9) continue;
				bestPrev = min(bestPrev, abs(prevPosition - actualPosition)+dp[letterNum-1][prevPosition]);
			}
			if(actualPosition){
				if(workOn[actualPosition-1] == goal[letterNum+1]){
					dp[letterNum][actualPosition-1] = 1 + bestPrev;
				}
			}
			if(actualPosition < (n-1)){
				if(workOn[actualPosition+1] == goal[letterNum+1]){
					dp[letterNum][actualPosition+1] = 1 + bestPrev;
				}
			}
		}
	}
	int ans = 1e9;
	for(int i = 0; i < n; ++i) ans = min(ans, dp[m-2][i]);
	if(ans == 1e9) cout << -1 << endl;
	else cout << ans << endl;
	return 0;
}

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