Submission #804762

#TimeUsernameProblemLanguageResultExecution timeMemory
804762tlnk07Bajka (COCI20_bajka)C++17
20 / 70
1083 ms212 KiB
#include<bits/stdc++.h> using namespace std; long long n, m, mini = INT_MAX; string s, str; vector<int> vec[30]; long long backtrack(int pos, int x) { if(x == m) return 0; long long temp = INT_MAX; for(int i : vec[s[pos] - 'a']) { if(i < n - 1 && s[i + 1] == str[x]) temp = min(temp, backtrack(i + 1, x + 1) + abs(pos - i) + 1); if(i > 0 && s[i - 1] == str[x]) temp = min(temp, backtrack(i - 1, x + 1) + abs(pos - i) + 1); } return temp; } int main() { cin >> n >> m >> s >> str; for(int i = 0; i < n; ++i) vec[s[i] - 'a'].push_back(i); for(int c : vec[str[0] - 'a']) mini = min(mini, backtrack(c, 1)); if(mini < INT_MAX) cout << mini; else cout << -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...