oj.uz

Submission #315884

# Submission time Handle Problem Language Result Execution time Memory
315884 2020-10-24T09:02:16 Z georgerapeanu Bajka (COCI20_bajka) C++11
0 / 70
 71 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(i == n){
                    dp[i][j] = min(dp[i][j],0);
                }
                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);

    cout << ans;

    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 760 KB Output is correct
2 Correct 63 ms 632 KB Output is correct
3 Correct 57 ms 632 KB Output is correct
4 Correct 66 ms 760 KB Output is correct
5 Incorrect 4 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -