oj.uz

Submission #315882

# Submission time Handle Problem Language Result Execution time Memory
315882 2020-10-24T08:50:33 Z georgerapeanu Bajka (COCI20_bajka) C++11
20 / 70
 14 ms 640 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;
                for(int k = 1;k <= n;k++){
                    if(j != k || i == m){
                        dp[i][j] = min(dp[i][j],dp[i + 1][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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct

Subtask #2
0 / 50.0

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