oj.uz

답안 #482254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482254 2021-10-23T22:27:33 Z s_samchenko Bajka (COCI20_bajka) C++17
70 / 70
 141 ms 1012 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;

void solve(){
	int n, m;
	string s, t;
	cin >> n >> m >> s >> t;
	
	s = "." + s + "."; t = "." + t + ".";
	vector < vector <int> > dp(n+1, vector <int> (m+1, inf));
	for (int i = 1; i <= n; ++i) dp[i][0] = 0;
	for (int i = 1; i <= n; ++i)
		if (s[i] == t[1]) dp[i][1] = 0;
	for (int j = 2; j <= m; ++j)
		for (int i = 1; i <= n; ++i){
			if (dp[i][j-1] == inf) continue;
			for (int k = 1; k <= n; ++k){
				if (k == i) continue;
				if (s[k] == t[j]){
					if (abs(k - i) == 1) dp[k][j] = min(dp[k][j], dp[i][j-1] + 1);
					if (s[k-1] == t[j-1]) dp[k][j] = min(dp[k][j], dp[i][j-1] + 1 + abs(k-1 - i));
					if (s[k+1] == t[j-1]) dp[k][j] = min(dp[k][j], dp[i][j-1] + 1 + abs(k+1 - i));
				}
			}
		}
	int ans = inf;
	for (int i = 1; i <= n; ++i) ans = min(ans, dp[i][m]);
	if (ans == inf) ans = -1;
	cout << ans;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 972 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 27 ms 972 KB Output is correct
8 Correct 141 ms 972 KB Output is correct
9 Correct 109 ms 1012 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 15 ms 972 KB Output is correct