Submission #881230

#TimeUsernameProblemLanguageResultExecution timeMemory
881230Ahmed_SolymanBajka (COCI20_bajka)C++14
70 / 70
83 ms780 KiB
/* In the name of Allah made by: Ahmed_Solyman */ #include <bits/stdc++.h> #include <ext/rope> using namespace std; using namespace __gnu_cxx; #pragma GCC optimize("-Ofast") #pragma GCC optimize("-O1") //-------------------------------------------------------------// typedef long long ll; typedef unsigned long long ull; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define PI acos(-1) #define lb lower_bound #define ub upper_bound #define endl '\n' #define all(v) v.begin(),v.end() #define allr(v) v.rbegin(),v.rend() #define sum_to(n) (n*(n+1))/2 #define pb push_back #define pf push_front #define fil(arr,x) memset(arr,x,sizeof(arr)) const ll mod=1e9+7; int dx[8]={0,1,0,-1,1,1,-1,-1}; int dy[8]={1,0,-1,0,1,-1,-1,1}; //-------------------------------------------------------------// ll lcm(ll a,ll b) { return (max(a,b)/__gcd(a,b))*min(a,b); } void person_bool(bool x) { cout<<(x?"YES":"NO")<<endl; } int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); #ifndef ONLINE_JUDGE //freopen("input.in", "r", stdin); //freopen("output.out", "w", stdout); #endif fast int n,m;cin>>n>>m; string a,b;cin>>a>>b; int dp[n][m]={}; for(int i=0;i<n;i++){ if(a[i]==b[0]){ dp[i][0]=0; } else{ dp[i][0]=1e9; } for(int j=1;j<m;j++)dp[i][j]=1e9; } for(int i=1;i<m;i++){ for(int j=0;j<n;j++){ if(a[j]==b[i]){ if(j+1<n){ dp[j][i]=min(dp[j][i],dp[j+1][i-1]+1); } if(j-1>=0){ dp[j][i]=min(dp[j][i],dp[j-1][i-1]+1); } } } for(int x=0;x<n;x++){ for(int y=0;y<n;y++){ if(a[x]==a[y]){ dp[x][i]=min(dp[x][i],dp[y][i]+abs(x-y)); dp[y][i]=min(dp[y][i],dp[x][i]+abs(x-y)); } } } } int ans=1e9; for(int i=0;i<n;i++)ans=min(ans,dp[i][m-1]); cout<<(ans==1e9?-1:ans)<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...