oj.uz

Submission #447837

# Submission time Handle Problem Language Result Execution time Memory
447837 2021-07-27T16:40:51 Z Apiram Bajka (COCI20_bajka) C++14
70 / 70
 25 ms 1004 KB 
#include <bits/stdc++.h>
using namespace std;

signed main() {
    int n,m; cin>>n>>m;
    string s,t; cin>>s>>t; 
    int64_t dp[m+2][n+2];

    for(int i = 0 ; i <= m ; i++) {
        for(int j = 0 ; j <= n+1 ; j++) {
            dp[i][j] = INT_MAX;
        }
    }

    for(int i = 0 ; i <= n+1 ; i++) dp[0][i]=0;

    for(int i = 0 ; i < m ; i++) {
        for(int j = 1 ; j <= n ; j++) {
        	  if(s[j-1] != t[i]) continue;
        	dp[i+1][j]=min(dp[i+1][j],min(dp[i][j-1],dp[i][j+1])+1);
          
            for(int k = 1 ; k <= n ; k++) {
                if(s[k-1] == t[i]) {
                    dp[i+1][k] = min(dp[i+1][k],dp[i+1][j] + abs(j-k));
                }
            }
        }
    }
  
    int64_t mn = INT_MAX;
    for(int i = 0 ; i <= n ; i++) {
        mn=min(mn,dp[m][i]);
    }
    if (mn==INT_MAX){
    	cout<<-1<<endl;
    }
    else
    cout << mn-1;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 972 KB Output is correct
2 Correct 5 ms 972 KB Output is correct
3 Correct 4 ms 972 KB Output is correct
4 Correct 5 ms 972 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 13 ms 992 KB Output is correct
8 Correct 24 ms 1004 KB Output is correct
9 Correct 25 ms 972 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 11 ms 992 KB Output is correct