Submission #525044

#	Time	Username	Problem	Language	Result	Execution time	Memory
525044		MOUF_MAHMALAT	Bajka (COCI20_bajka)	C++14	70 / 70	45 ms	1100 KiB

bajka

#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef int ll;
ll n,m,dp[2][309][309];
string s,c;
vector<vector<ll> >v;
ll best(bool b,ll i,ll j)
{
    if(j==m)
        return 0;
    ll &r=dp[b][i][j];
    if(r!=-1)
        return r;
    r=1e9;
    if(i&&s[i-1]==c[j])
        r=min(r,best(0,i-1,j+1)+1);
    if(i+1<n&&s[i+1]==c[j])
        r=min(r,best(0,i+1,j+1)+1);
    if(!b)
        for(auto&z:v[s[i]-'a'])
            r=min(r,best(1,z,j)+abs(i-z));
    return r;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s>>c;
    v.resize(26);
    for(ll i=0; i<n; i++)
        v[s[i]-'a'].push_back(i);
    memset(dp,-1,sizeof dp);
    ll ans=1e9;
    for(ll i=0;i<n;i++)
        if(s[i]==c[0])
        ans=min(ans,best(0,i,1));
    if(ans>=1e9)
    ans=-1;
    cout<<ans;
    return 0;
}

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