oj.uz

Submission #366409

# Submission time Handle Problem Language Result Execution time Memory
366409 2021-02-14T06:54:50 Z VEGAnn Bajka (COCI20_bajka) C++14
70 / 70
 13 ms 768 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 7 ms 748 KB Output is correct
8 Correct 13 ms 748 KB Output is correct
9 Correct 12 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 5 ms 768 KB Output is correct