oj.uz

Submission #401137

# Submission time Handle Problem Language Result Execution time Memory
401137 2021-05-09T12:41:18 Z jenkinsser Bajka (COCI20_bajka) C++17
70 / 70
 77 ms 1048 KB 
#include <bits/stdc++.h>
#define FOR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define for0(ii,bb) FOR(ii,0,bb)
#define for1(ii,bb) FOR(ii,1,bb+1)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define piii pair<int,pii>
#define piiii pair<pii,pii>
#define pdi pair<double,int>
#define vi vector<int>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define int ll

using namespace std;

const int N = 305;
const int INF = 1e9+5;
const int mod = 998244353;

int n,m;
string s,t;

signed main(){
    fastio()
    cin >> n >> m >> s >> t;
    vector<vector<int>> dp(N,vector<int>(N,INF));
    for(int i=0;i<n;i++)
        if(s[i]==t[0])
            dp[0][i]=0;
    for(int i=1;i<m;i++){
        for(int j=0;j<n;j++){
            if(s[j]==t[i]){
                if(j>0){
                    dp[i][j]=min(dp[i-1][j-1]+1,dp[i][j]);
                }
                if(j<n-1){
                    dp[i][j]=min(dp[i-1][j+1]+1,dp[i][j]);
                }
            }
        }
        for(int j=0;j<n;j++){
            if(s[j]!=t[i])continue;
            for(int k=0;k<n;k++){
                if(s[k]!=t[i])continue;
                dp[i][j]=min(dp[i][j],dp[i][k]+abs(j-k));
            }
        }
    }
    int ans=INF;
    for(int i=0;i<n;i++)
        ans=min(ans,dp[m-1][i]);
    cout << (ans==INF?-1:ans) << nl;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 960 KB Output is correct
6 Correct 1 ms 956 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 972 KB Output is correct
2 Correct 9 ms 972 KB Output is correct
3 Correct 5 ms 972 KB Output is correct
4 Correct 5 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 19 ms 972 KB Output is correct
8 Correct 44 ms 972 KB Output is correct
9 Correct 77 ms 972 KB Output is correct
10 Correct 1 ms 972 KB Output is correct
11 Correct 17 ms 1048 KB Output is correct