oj.uz

Submission #636201

# Submission time Handle Problem Language Result Execution time Memory
636201 2022-08-28T13:46:59 Z nguyen31hoang08minh2003 Bajka (COCI20_bajka) C++14
70 / 70
 118 ms 2348 KB 
/*
\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/
\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//
/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\
\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/
/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\
\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/
/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\
\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/
//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\
/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\
\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/
\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//
/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\
\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/
/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\
\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/
/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\
\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/
//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\
/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define maxN 305
#define maxM 305
const int inf = 0X3F3F3F3F;

int n, m, d[maxN][maxM];
string s, t;
priority_queue<array<int, 3>, vector<array<int, 3> >, greater<array<int, 3> > > pq;

void pushQueue(const int x, const int y, const int w) {
    if (mini(d[x][y], w)) {
        if (y >= m) {
            cout << d[x][y] << '\n';
            exit(0);
        }
        pq.push({d[x][y], x, y});
    }
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
//        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(d, inf, sizeof(d));
    cin >> n >> m >> s >> t;
    fore(i, 0, n) {
        if (s[i] != t[0])
            continue;
        pushQueue(i, 1, 0);
    }
    for (; !pq.empty();) {
        const auto [w, x, y] = pq.top();
        pq.pop();
        if (w != d[x][y])
            continue;
        if (x > 0 && s[x - 1] == t[y])
            pushQueue(x - 1, y + 1, w + 1);
        if (x + 1 < n && s[x + 1] == t[y])
            pushQueue(x + 1, y + 1, w + 1);
        fore(i, 0, n)
            if (s[x] == s[i])
                pushQueue(i, y, w + abs(x - i));
    }
    cout << -1 << '\n';
    return 0;
}

Compilation message

bajka.cpp: In function 'int main()':
bajka.cpp:81:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |         const auto [w, x, y] = pq.top();
      |                    ^

Subtask #1
20.0 / 20.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 6 ms 708 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 696 KB Output is correct
7 Correct 31 ms 980 KB Output is correct
8 Correct 118 ms 2348 KB Output is correct
9 Correct 41 ms 1492 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 22 ms 852 KB Output is correct