oj.uz

Submission #676141

# Submission time Handle Problem Language Result Execution time Memory
676141 2022-12-29T12:54:28 Z esomer Bajka (COCI20_bajka) C++17
70 / 70
 56 ms 668 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define endl "\n"
 
const int MOD = 998244353;

void solve(){
	int n, m; cin >> n >> m;
	string s; cin >> s; 
	string t; cin >> t;
	vector<vector<int>> dp(m, vector<int>(n, -1));
	for(int i = 0; i < n; i++){
		if(s[i] == t[0]) dp[0][i] = 0;
	}
	for(int i = 1; i < m; i++){
		for(int j = 0; j < n; j++){
			if(dp[i - 1][j] == -1) continue;
			for(int q = 0; q < n; q++){
				if(q == j) continue;
				if(s[q] == t[i]){
					if(q == j + 1 || q == j - 1){
						if(dp[i][q] == -1) dp[i][q] = dp[i - 1][j] + 1;
						else dp[i][q] = min(dp[i][q], dp[i - 1][j] + 1);
					}else if(q + 1 < n && s[q + 1] == s[j]){
						int cost = dp[i - 1][j] + abs(q + 1 - j) + 1;
						if(dp[i][q] == -1) dp[i][q] = cost;
						else dp[i][q] = min(dp[i][q], cost);
					}else if(q - 1 < n && s[q - 1] == s[j]){
						int cost = dp[i - 1][j] + abs(q - 1 - j) + 1;
						if(dp[i][q] == -1) dp[i][q] = cost;
						else dp[i][q] = min(dp[i][q], cost);
					}
				}
			}
		}
		for(int j = 0; j < n; j++){
			if(dp[i][j] == -1) continue;
			for(int q = 0; q < n; q++){
				if(s[q] != s[j]) continue;
				if(dp[i][q] == -1) dp[i][q] = dp[i][j] + abs(q - j);
				else dp[i][q] = min(dp[i][q], dp[i][j] + abs(q - j));
			}
		}
	}
	int ans = -1;
	for(int i = 0; i < n; i++){
		if(dp[m - 1][i] != -1){
			if(ans == -1) ans = dp[m - 1][i];
			else ans = min(ans, dp[m - 1][i]);
		}
	}
	cout << ans << endl;
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    //int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

Subtask #1
20.0 / 20.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 6 ms 580 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 25 ms 596 KB Output is correct
8 Correct 56 ms 668 KB Output is correct
9 Correct 52 ms 664 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 20 ms 596 KB Output is correct