Submission #319523

#TimeUsernameProblemLanguageResultExecution timeMemory
319523gustasonBajka (COCI20_bajka)C++14
20 / 70
1093 ms868 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; map<char, vector<int>> mp; // positions where a letter shows up const int INF = 1e9 + 5; int n, m, ans = INF; string scary, fav; vector<vector<int>> dp(305, vector<int>(305, INF)); void go(int at, int id, int cost, bool used2) { if (cost < dp[at][id]) { dp[at][id] = cost; } else return; if (id == m-1) { ans = min(ans, cost); //cout << at << " " << id << " " << cost << " " << used2 << "\n"; return; } // use move1 // go left if (at > 0 && scary[at-1] == fav[id+1]) { go(at - 1, id+1, cost + 1, 0); } // go right if (at < n-1 && scary[at+1] == fav[id+1]) { go(at + 1, id+1, cost + 1, 0); } // use move2 if (used2) return; for(int i : mp[scary[at]]) { go(i, id, cost + abs(at - i), 1); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> scary >> fav; for(int i = 0; i < n; i++) { mp[scary[i]].push_back(i); } for(int i : mp[fav[0]]) { go(i, 0, 0, 1); } cout << (ans >= INF ? -1 : ans) << "\n"; return 0; } //~ check for overflows
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...