Submission #720598

#	Time	Username	Problem	Language	Result	Execution time	Memory
720598		trucmai	Bajka (COCI20_bajka)	C++17	70 / 70	97 ms	1576 KiB

bajka

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "

const int MN1 = 1e6 + 5,MN2 = 1e4 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;

ll n,m,f[400][400]; 
string a,b; 

//f[i][j] 

ll dp(ll i,ll j){
  if(j == m) return 0; 
  ll &res = f[i][j];
  if(res != -1) return res;
  res = INF;
  for(ll k = 0;k < n;++k)
    if(a[k] == a[i])
      for(ll p = -1;p < 2;++p){
        if(!p || k + p < 0 || k + p >= n) continue; 
        if(a[k + p] != b[j]) continue; 
        res = min(res,dp(k+p,j+1) + abs(k - i) + 1);      
      }
  return res; 
}

void solve(){
  cin>>n>>m>>a>>b;
  mset(f,-1);
  ll ans = INF;
  for(ll i = 0;i < n;++i)
    if(a[i] == b[0]) ans = min(ans,dp(i,1));
  cout<<(ans >= INF ? -1 : ans);
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);
  //freopen("i.inp","r",stdin);
  //freopen("o.out","w",stdout);
  ll t = 1; //cin>>t; 
  while(t--) solve();
}

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