Submission #495657

#	Time	Username	Problem	Language	Result	Execution time	Memory
495657		AlperenT	Bajka (COCI20_bajka)	C++17	70 / 70	40 ms	324 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]){
                if(i - 1 >= 0 && prv[i - 1] != INF) cur[i] = min(cur[i], prv[i - 1] + 1);
                if(i + 1 < n && prv[i + 1] != INF) cur[i] = min(cur[i], prv[i + 1] + 1);
            }
        }

        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] && cur[j] != INF){
                        cur[i] = min(cur[i], cur[j] + (i - j));
                    }
                }

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

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

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

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

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