oj.uz

Submission #661127

# Submission time Handle Problem Language Result Execution time Memory
661127 2022-11-24T15:10:17 Z faik Bajka (COCI20_bajka) C++17
70 / 70
 2 ms 980 KB 
#include "bits/stdc++.h"

using namespace std;

#define MOD 1000000007

#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int,int> pii;

ll fastpow(ll a, ll b){
	ll ret = 1;
	while(b){
		if(b%2)
			ret = ret*a%MOD;
		a = a*a%MOD;
		b >>= 1;
	}
	return ret;
}

ll dp[310][310];

void solve(){
	ll n,m;cin >> n >> m;
	string nstr;cin >> nstr;
	string mstr;cin >> mstr;

	for(int i = 0;i < n;i++){
		if(nstr[i] != mstr[0])
			dp[i][0] = INT_MAX;
	}

	for(int i = 1;i < m;i++){
		for(int j = 0;j < n;j++){
			dp[j][i] = INT_MAX;
			if(nstr[j] != mstr[i])
				continue;
			if(j != 0){
				dp[j][i] = dp[j-1][i-1]+1;
			}
			if(j != n-1){
				dp[j][i] = min(dp[j][i], dp[j+1][i-1]+1);
			}
		}
		ll current = INT_MAX;
		for(int j = 0;j < n;j++){
			current++;
			if(nstr[j] != mstr[i])
				continue;
			dp[j][i] = min(dp[j][i], current);
			current = dp[j][i];
		}
		current = INT_MAX;
		for(int j = n-1;j >= 0;j--){
			current++;
			if(nstr[j] != mstr[i])
				continue;
			dp[j][i] = min(dp[j][i], current);
			current = dp[j][i];
		}
	}
	// for(int j = 0;j < m;j++){
	// 	for(int i = 0;i < n;i++){
	// 		cout << dp[i][j] << ' ';
	// 	}
	// 	cout << '\n';
	// }
	ll ret = INT_MAX;
	for(int i = 0;i < n;i++){
		ret = min(ret,dp[i][m-1]);
	}
	if(ret == INT_MAX)
		ret = -1;
	cout << ret;
}

signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
#ifdef DEBUG
	freopen("i","r",stdin);
	freopen("o","w",stdout);
#endif
	int q = 1;
#ifdef TEST
	cin >> q;
#endif
	while(q--)
		solve();
}
//Unimaginative; 
//over-literal; 
//lacking nuance; 
//lacking in sub-text; 
//too obvious; 
//having neither subtlety nor sophistication;

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 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
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 1 ms 964 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 964 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct