Submission #315884

#	Time	Username	Problem	Language	Result	Execution time	Memory
315884		georgerapeanu	Bajka (COCI20_bajka)	C++11	0 / 70	71 ms	760 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;
                if(i == n){
                    dp[i][j] = min(dp[i][j],0);
                }
                if(j > 1){
                    dp[i][j] = min(dp[i][j],1 + dp[i + 1][j - 1]);
                }
                if(j < n){
                    dp[i][j] = min(dp[i][j],1 + dp[i + 1][j + 1]);
                }
            }
        }
        for(int j = 1;j <= n;j++){
            for(int k = 1;k <= n;k++){
                if(s[j] == s[k]){
                    dp[i][j] = min(dp[i][j],dp[i][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