Submission #870578

#TimeUsernameProblemLanguageResultExecution timeMemory
870578epicci23Bajka (COCI20_bajka)C++17
20 / 70
1059 ms1116 KiB
#include "bits/stdc++.h" using namespace std; #define pb push_back #define endl "\n" #define int long long #define sz(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH * SIMPLIFY THE PROBLEM * READ THE STATEMENT CAREFULLY !!! if there is an specified/interesting smth(i.e. constraint) in the statement, then you must be careful about that */ const int INF = 1e18; int dp[305][305]; int n,m; string s,t; int f(int a,int b){ if(a==m) return 0; if(dp[a][b]!=INF) return dp[a][b]; int cevv=INF; for(int i=0;i<n;i++){ if(s[b]!=s[i]) continue; if(i-1>=0 && s[i-1]==t[a]) cevv=min(cevv,f(a+1,i-1)+1+abs(i-b)); if(i+1<n && s[i+1]==t[a]) cevv=min(cevv,f(a+1,i+1)+1+abs(i-b)); } return dp[a][b]=cevv; } void solve(){ cin >> n >> m; cin >> s >> t; for(int i=0;i<305;i++){ for(int j=0;j<305;j++){ dp[i][j]=INF; } } int ans=INF; for(int i=0;i<n;i++){ if(s[i]==t[0]){ ans=min(ans,f(1,i)); } } if(ans==INF) cout << -1 << endl; else cout << ans << endl; } int32_t main(){ cin.tie(0); ios::sync_with_stdio(0); int t=1;//cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...