Submission #495653

#	Time	Username	Problem	Language	Result	Execution time	Memory
495653		AlperenT	Bajka (COCI20_bajka)	C++17	20 / 70	1 ms	320 KiB

bajka

#include <bits/stdc++.h>

using namespace std;

const int N = 300 + 5, INF = 1e9 + 5;

int n, m, prv[N], cur[N], ans;

string a, b;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> m;

    cin >> a >> b;

    fill(prv, prv + n, INF);

    for(int i = 0; i < n; i++) if(a[i] == b[0]) prv[i] = 0;

    for(int c = 1; c < m; c++){
        fill(cur, cur + n, INF);
        for(int i = 0; i < n; i++){
            if(a[i] == b[c]){
                for(int j = i - 1; j >= 0; j--){
                    if(a[j] == b[c - 1]){
                        cur[i] = min(cur[i], prv[j] + (i - j));
                        break;
                    }
                }

                for(int j = i + 1; j < n; j++){
                    if(a[j] == b[c - 1]){
                        cur[i] = min(cur[i], prv[j] + (j - i));
                        break;
                    }
                }
            }
        }

        copy(cur, cur + n, prv);
    }

    ans = *min_element(prv, prv + n);

    cout << (ans == INF ? -1 : ans);
}

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