oj.uz

Submission #468031

# Submission time Handle Problem Language Result Execution time Memory
468031 2021-08-26T00:43:55 Z Marceantasy Bajka (COCI20_bajka) C++17
70 / 70
 28 ms 692 KB 
#include <bits/stdc++.h>
using namespace std; 

#define ll long long; 
#define ar array; 

const int mxN = 310, M = 1e9+7; 
int n, m, dp[mxN][mxN];
string s, p;  

int solve(int a, int b){
    if(b == m) return 0; 
    if(~dp[a][b]){
        return dp[a][b];
    }
    int act = 1e9;
    for(int i = 0; i<n; ++i){
        if(s[i] == s[a]){
            if(i-1 >= 0 && s[i-1] == p[b]){
                act = min(act, solve(i-1, b+1) + abs(a-i)+1);
            }
            if(i+1 < n && s[i+1] == p[b]){
                act = min(act, solve(i+1, b+1) + abs(a-i)+1);
            }
        }
    }
    return dp[a][b] = act;
}

int main(){
    cin >> n >> m; 
    cin >> s >> p; 
    memset(dp, -1, sizeof(dp));
    int ans = 1e9; 
    for(int i = 0; i<n; ++i){
        if(s[i] == p[0]){
            ans = min(ans, solve(i, 1));
        }
    }
    if(ans >= 1e9){
        cout << -1 << "\n"; 
    }else{
        cout << ans << "\n"; 
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 560 KB Output is correct
3 Correct 1 ms 556 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 7 ms 588 KB Output is correct
8 Correct 26 ms 692 KB Output is correct
9 Correct 28 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 4 ms 684 KB Output is correct