Submission #804775

#TimeUsernameProblemLanguageResultExecution timeMemory
804775tlnk07Bajka (COCI20_bajka)C++17
70 / 70
26 ms980 KiB
#include<bits/stdc++.h> using namespace std; long long n, m, mini = INT_MAX, val[301][301]; string s, str; vector<int> vec[30]; long long backtrack(int pos, int x) { if(val[pos][x]) return val[pos][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); } val[pos][x] = temp; return temp; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 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...