oj.uz

Submission #741727

# Submission time Handle Problem Language Result Execution time Memory
741727 2023-05-14T17:14:34 Z a_aguilo Bajka (COCI20_bajka) C++14
20 / 70
 5 ms 664 KB 
#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;
	}
	if(n == 1){
		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){
				//cout << actualPosition << " " << prevPosition << " " << dp[letterNum-1][prevPosition] << endl;
				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.0 / 20.0

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

Subtask #2
0 / 50.0

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