oj.uz

Submission #315885

# Submission time Handle Problem Language Result Execution time Memory
315885 2020-10-24T09:03:34 Z georgerapeanu Bajka (COCI20_bajka) C++11
70 / 70
 102 ms 892 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 == m){
                        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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 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
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 632 KB Output is correct
2 Correct 50 ms 632 KB Output is correct
3 Correct 42 ms 760 KB Output is correct
4 Correct 43 ms 684 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 65 ms 632 KB Output is correct
8 Correct 60 ms 636 KB Output is correct
9 Correct 102 ms 892 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 65 ms 632 KB Output is correct