oj.uz

Submission #315883

# Submission time Handle Problem Language Result Execution time Memory
315883 2020-10-24T08:57:40 Z georgerapeanu Bajka (COCI20_bajka) C++11
50 / 70
 100 ms 760 KB 
#include <bits/stdc++.h>

using namespace std;

int n,m;

int dp[305][305];
string s;
string t;

int main(){
    cin >> n >> m;
    cin >> s;
    cin >> t;

    s = " " + s;
    t = " " + t;

    for(int i = m;i;i--){
        for(int j = 1;j <= n;j++){
            if(s[j] != t[i]){
                dp[i][j] = 1e9;
            }
            else{
                dp[i][j] = 1e9;
                if(j > 1){
                    dp[i][j] = min(dp[i][j],1 + dp[i + 1][j - 1]);
                }
                if(j < n){
                    dp[i][j] = min(dp[i][j],1 + dp[i + 1][j + 1]);
                }
            }
        }
        for(int j = 1;j <= n;j++){
            for(int k = 1;k <= n;k++){
                if(s[j] == s[k]){
                    dp[i][j] = min(dp[i][j],dp[i][k] + abs(j - k));
                }
            }
        }
    }

    int ans = 1e9;

    for(int i = 1;i <= n;i++){
        ans = min(ans,dp[1][i]);
    }

    ans = (ans >= 1e9 ? -1:ans - 1);

    cout << ans;

    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 632 KB Output is correct
2 Correct 53 ms 640 KB Output is correct
3 Correct 42 ms 680 KB Output is correct
4 Correct 46 ms 632 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 67 ms 632 KB Output is correct
8 Correct 59 ms 760 KB Output is correct
9 Correct 100 ms 632 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 66 ms 632 KB Output is correct