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>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 1010
#define MOD 1000000007
#define ln '\n'
ll arr[MAX][MAX];
signed main() {
ll N, M;
cin >> N >> M;
string s1, s2;
cin >> s1 >> s2;
ll i, j;
for (i = 0; i < N; i++) {
if (s1[i] != s2[0]) arr[0][i] = 1010101010;
}
for (i = 1; i < M; i++) {
vector<ll> pr;
for (j = 0; j < N; j++) {
if (s1[j] == s2[i - 1]) pr.push_back(j);
}
ll chk = 0;
for (j = 0; j < N; j++) {
arr[i][j] = 101010101010;
if (s1[j] == s2[i]) {
for (auto k : pr) {
if (k == j) continue;
chk = 1;
arr[i][j] = min(arr[i][j], abs(k - j) + arr[i - 1][k]);
}
}
}
}
ll ans = 1010101010;
for (i = 0; i < N; i++) ans = min(ans, arr[M - 1][i]);
if (ans == 1010101010) cout << -1 << ln;
else cout << ans << ln;
}
Compilation message (stderr)
bajka.cpp: In function 'int main()':
bajka.cpp:27:6: warning: variable 'chk' set but not used [-Wunused-but-set-variable]
27 | ll chk = 0;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |