oj.uz

답안 #495657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
495657 2021-12-19T19:25:46 Z AlperenT Bajka (COCI20_bajka) C++17
70 / 70
 40 ms 324 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]){
                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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 204 KB Output is correct
2 Correct 4 ms 324 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 12 ms 208 KB Output is correct
8 Correct 24 ms 208 KB Output is correct
9 Correct 40 ms 208 KB Output is correct
10 Correct 0 ms 316 KB Output is correct
11 Correct 8 ms 208 KB Output is correct