oj.uz

Submission #319523

# Submission time Handle Problem Language Result Execution time Memory
319523 2020-11-05T13:25:15 Z gustason Bajka (COCI20_bajka) C++14
20 / 70
 1000 ms 868 KB 
#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

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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 748 KB Output is correct
2 Correct 167 ms 864 KB Output is correct
3 Correct 151 ms 868 KB Output is correct
4 Correct 249 ms 868 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Execution timed out 1093 ms 748 KB Time limit exceeded
8 Halted 0 ms 0 KB -