oj.uz

Submission #495653

# Submission time Handle Problem Language Result Execution time Memory
495653 2021-12-19T19:16:35 Z AlperenT Bajka (COCI20_bajka) C++17
20 / 70
 1 ms 320 KB 
#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.0 / 20.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 316 KB Output isn't correct
2 Halted 0 ms 0 KB -