Submission #315880

#	Time	Username	Problem	Language	Result	Execution time	Memory
315880		georgerapeanu	Bajka (COCI20_bajka)	C++11	0 / 70	14 ms	640 KiB

bajka

#include <bits/stdc++.h>

using namespace std;

int n,m;

int dp[305][305];
string s;
string t;

int main(){
    cin >> n >> m;
    cin >> s;
    cin >> t;

    s = " " + s;
    t = " " + t;

    for(int i = m;i;i--){
        for(int j = 1;j <= n;j++){
            if(s[j] != t[i]){
                dp[i][j] = 1e9;
            }
            else{
                dp[i][j] = 1e9;
                for(int k = 1;k <= n;k++){
                    if(j != k){
                        dp[i][j] = min(dp[i][j],dp[i + 1][k] + abs(j - k));
                    }
                }
            }
        }
    }

    int ans = 1e9;

    for(int i = 1;i <= n;i++){
        ans = min(ans,dp[1][i]);
    }

    ans = (ans >= 1e9 ? -1:ans);

    cout << ans;

    return 0;
}

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