oj.uz

Submission #922234

# Submission time Handle Problem Language Result Execution time Memory
922234 2024-02-05T09:32:09 Z blackavar Bajka (COCI20_bajka) C++14
70 / 70
 1 ms 604 KB 
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e3 + 10;
int dp[250][N];
vector<int> pos[26];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    for(int i = 0; i < n; ++i) pos[s[i] - 'a'].push_back(i);
/*
7 7
monolog
nogolom
*/
    bool st = 0;
    for(int i = 0; i < n; ++i) dp[st][i] = 1e9;
    for(auto &p : pos[t[0] - 'a']) dp[st][p] = 0;
    int f = 0;
    for(int i = 1; i < m; ++i) {
        if(pos[t[i] - 'a'].empty()) break;
        st = 1 - st;
        for(int j = 0; j < n; ++j) dp[st][j] = 1e9;
        for(auto &p1 : pos[t[i] - 'a']) {
            if(p1 != 0 && s[p1 - 1] == t[i - 1]) dp[st][p1] = min(dp[st][p1], dp[1 - st][p1 - 1] + 1);
            if(p1 != n - 1 && s[p1 + 1] == t[i - 1]) dp[st][p1] = min(dp[st][p1], dp[1 - st][p1 + 1] + 1);
        }
        int l = pos[t[i] - 'a'][0], r = pos[t[i]- 'a'].back();
        int tmp = 1e9;
        for(int j = l; j <= r; ++j, ++tmp) {
            if(s[j] != t[i]) continue;
            tmp = dp[st][j] = min(tmp, dp[st][j]);
        }
        tmp = 1e9;
        for(int j = r; j >= l; --j, ++tmp) {
            if(s[j] != t[i]) continue;
            tmp = dp[st][j] =  min(tmp, dp[st][j]);
        }
    }
    int ans = 1e9;
    for(int i = 0; i < n; ++i) 
        ans = min(ans, dp[st][i]);
    cout << (ans >= 1e9 ? -1 : ans);
    return 0;
}

Compilation message

bajka.cpp: In function 'int main()':
bajka.cpp:25:9: warning: unused variable 'f' [-Wunused-variable]
   25 |     int f = 0;
      |         ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct