oj.uz

Submission #741718

# Submission time Handle Problem Language Result Execution time Memory
741718 2023-05-14T16:41:10 Z a_aguilo Bajka (COCI20_bajka) C++14
0 / 70
 4 ms 596 KB 
#include<bits/stdc++.h>

using namespace std;

int n, m;
string workOn, goal;

int main(){
	cin >> n >> m;
	cin >> workOn >> goal;
	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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Incorrect 4 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -