This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define endl '\n'
const ll MOD = 1e9+7;
const ll INF = 1e16;
const ll MAX = 2 * 1e5;
char getLast(string s){
return s[s.size()-1];
}
void solve(){
int n,m;
cin>>n>>m;
string a,b; cin>>a>>b;
vector<ll> dp(n, INF);
for(int i = 0; i < n; i++){
if(a[i] == getLast(b)){
dp[i] = 0;
}
}
while(b.size() > 1){
char top = getLast(b);
b.pop_back();
#ifdef DEBUG
for(int z : dp){
cout<<z<<" ";
}
#endif
char cur = getLast(b);
vector<ll> temp(n, INF);
bool check = false;
for(ll i = 0; i < n; i++){
if(a[i] != top) continue;
if(i - 1 >= 0 && a[i-1] == cur){
check = true;
temp[i-1] = min(dp[i] + 1, temp[i-1]);
for(ll j = i-2; j >= 0; j--){
if(a[j] == cur){
temp[j] = min((i-1) - j + temp[i - 1], temp[j]);
}
}
}
if(i + 1 < n && a[i+1] == cur){
check = true;
temp[i+1] = min(dp[i] + 1, temp[i+1]);
for(ll j = i+2; j < n; j++){
if(a[j] == cur){
temp[j] = min(j - (i + 1) + temp[i + 1], temp[j]);
}
}
}
}
dp = temp;
if(!check){
cout<<-1;
return;
}
}
#ifdef DEBUG
for(int z : dp){
cout<<z<<" ";
}
#endif
ll ans = INF;
for(ll z : dp){
ans = min(z, ans);
}
cout<<(ans == INF?-1:ans);
}
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(NULL);
int t = 1;
//cin>>t;
int temp = t;
while(t--){
//cout<<"Case #"<<temp - t<<" > "<<endl;
solve();
cout<<endl;
}
cout.flush();
}
Compilation message (stderr)
bajka.cpp: In function 'int main()':
bajka.cpp:105:9: warning: unused variable 'temp' [-Wunused-variable]
105 | int temp = t;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |