Submission #319560

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