oj.uz

Submission #525044

# Submission time Handle Problem Language Result Execution time Memory
525044 2022-02-10T14:53:13 Z MOUF_MAHMALAT Bajka (COCI20_bajka) C++14
70 / 70
 45 ms 1100 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct

Subtask #2
50.0 / 50.0

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