oj.uz

Submission #319569

# Submission time Handle Problem Language Result Execution time Memory
319569 2020-11-05T14:10:56 Z gustason Bajka (COCI20_bajka) C++14
70 / 70
 84 ms 748 KB 
#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, -1));

int go(int at, int id) {
    if (id == m-1) {
        return 0;
    }
    if (dp[at][id] != -1) {
        return dp[at][id];
    }

    int ret = INF;

    for(int i = 0; i < n; i++) {
        if (scary[at] == scary[i]) {
            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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 12 ms 748 KB Output is correct
8 Correct 72 ms 748 KB Output is correct
9 Correct 84 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 7 ms 748 KB Output is correct