Submission #366409

#	Time	Username	Problem	Language	Result	Execution time	Memory
366409		VEGAnn	Bajka (COCI20_bajka)	C++14	70 / 70	13 ms	768 KiB

bajka

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define i3 array<int,3>
using namespace std;
const int N = 310;
const int oo = 2e9;
set<i3> st;
int n, m, lft[N], rgt[N], dst[N][N];
string good, bad;

void upd(int ni, int nj, int NW){
    if (ni >= 0 && ni < n && bad[ni] == good[nj - 1] && dst[ni][nj] > NW){
        st.erase({dst[ni][nj], ni, nj});
        dst[ni][nj] = NW;
        st.insert({dst[ni][nj], ni, nj});
    }
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m >> bad >> good;

    for (int i = 0; i < n; i++){
        lft[i] = rgt[i] = -1;

        for (int j = i - 1; j >= 0; j--)
            if (bad[i] == bad[j]){
                lft[i] = j;
                break;
            }

        for (int j = i + 1; j < n; j++)
            if (bad[i] == bad[j]){
                rgt[i] = j;
                break;
            }
    }

    for (int i = 0; i < n; i++)
    for (int j = 1; j <= m; j++)
        dst[i][j] = oo;

    for (int i = 0; i < n; i++)
        if (bad[i] == good[0]){
            dst[i][1] = 0;

            st.insert({0, i, 1});
        }

    while (sz(st) > 0){
        i3 CR = (*st.begin()); st.erase(st.begin());

        int i = CR[1], j = CR[2];

        upd(i - 1, j + 1, CR[0] + 1);
        upd(i + 1, j + 1, CR[0] + 1);

        upd(lft[i], j, CR[0] + abs(i - lft[i]));
        upd(rgt[i], j, CR[0] + abs(i - rgt[i]));
    }

    int ans = oo;

    for (int i = 0; i < n; i++)
        ans = min(ans, dst[i][m]);

    if (ans == oo) ans = -1;

    cout << ans;

    return 0;
}

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