Submission #470330

#	Time	Username	Problem	Language	Result	Execution time	Memory
470330		mychecksedad	Bajka (COCI20_bajka)	C++17	70 / 70	56 ms	672 KiB

bajka

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 310, F = 1e9;


int n, m, dp[N][N], ans = F;
string s, t;

int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n >> m >> s >> t;
	for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) dp[i][j] = F;
	s = ' ' + s + ' ';
	t = ' ' + t + ' ';
	for(int i = 1; i <= m; i++){
		vector<int> v;
		for(int j = 1; j <= n; j++) if(s[j] == t[i]) v.pb(j);
		for(int pos: v){
			dp[i][pos] = (i==1?0:F);
			if(i > 1){
				if(s[pos - 1] == t[i - 1]){
					dp[i][pos] = min(dp[i][pos], dp[i - 1][pos - 1] + 1);
				}
				if(s[pos + 1] == t[i - 1]){
					dp[i][pos] = min(dp[i][pos], dp[i - 1][pos + 1] + 1);
				}
			}
		}
		for(int j = 0; j < v.size(); j++){
			for(int k = 0; k < v.size(); k++){
				dp[i][v[j]] = min(dp[i][v[j]], abs(v[j] - v[k]) + dp[i][v[k]]);
			}
			if(i == m){
				ans = min(ans, dp[i][v[j]]);
			}
		}
	}
	cout << (ans==F ? -1 : ans);

	return 0;
}

Compilation message (stderr)

bajka.cpp: In function 'int main()':
bajka.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int j = 0; j < v.size(); j++){
      |                  ~~^~~~~~~~~~
bajka.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for(int k = 0; k < v.size(); k++){
      |                   ~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50