Submission #448165

#TimeUsernameProblemLanguageResultExecution timeMemory
448165flappybirdBajka (COCI20_bajka)C++14
20 / 70
7 ms2124 KiB
#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]); } } } if (!chk) { cout << -1 << ln; return 0; } } ll ans = 1010101010; for (i = 0; i < N; i++) { if (s1[i] == s2[M - 1]) ans = min(ans, arr[M - 1][i]); } cout << ans << ln; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...