Submission #401137

#	Time	Username	Problem	Language	Result	Execution time	Memory
401137		jenkinsser	Bajka (COCI20_bajka)	C++17	70 / 70	77 ms	1048 KiB

bajka

#include <bits/stdc++.h>
#define FOR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define for0(ii,bb) FOR(ii,0,bb)
#define for1(ii,bb) FOR(ii,1,bb+1)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define piii pair<int,pii>
#define piiii pair<pii,pii>
#define pdi pair<double,int>
#define vi vector<int>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define int ll

using namespace std;

const int N = 305;
const int INF = 1e9+5;
const int mod = 998244353;

int n,m;
string s,t;

signed main(){
    fastio()
    cin >> n >> m >> s >> t;
    vector<vector<int>> dp(N,vector<int>(N,INF));
    for(int i=0;i<n;i++)
        if(s[i]==t[0])
            dp[0][i]=0;
    for(int i=1;i<m;i++){
        for(int j=0;j<n;j++){
            if(s[j]==t[i]){
                if(j>0){
                    dp[i][j]=min(dp[i-1][j-1]+1,dp[i][j]);
                }
                if(j<n-1){
                    dp[i][j]=min(dp[i-1][j+1]+1,dp[i][j]);
                }
            }
        }
        for(int j=0;j<n;j++){
            if(s[j]!=t[i])continue;
            for(int k=0;k<n;k++){
                if(s[k]!=t[i])continue;
                dp[i][j]=min(dp[i][j],dp[i][k]+abs(j-k));
            }
        }
    }
    int ans=INF;
    for(int i=0;i<n;i++)
        ans=min(ans,dp[m-1][i]);
    cout << (ans==INF?-1:ans) << nl;
}

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