oj.uz

Submission #988671

# Submission time Handle Problem Language Result Execution time Memory
988671 2024-05-25T13:18:42 Z coolboy19521 Kamenčići (COCI21_kamencici) C++17
0 / 70
 1 ms 348 KB 
// Untill Addiction Stops.

# pragma GCC optimize("Ofast")
# include <bits/stdc++.h>

namespace ddr {
    # define bpc(bt) __builtin_popcountll(bt)
    # define bcl(bt) __builtin_clz(bt)
    # define alr(v) rbegin(v), rend(v)
    # define all(v) begin(v), end(v)
    # define si(v) ((ll)v.size())
    # define lob lower_bound
    # define upb upper_bound
    # define pub push_back
    # define pob pop_back
    # define mp make_pair
    # define ins insert
    # define se second
    # define fi first

    template <class T, size_t N> using ar = std::array <T, N>;
    template <class T, class U> using pi = std::pair <T, U>;
    template <class T> using pq = std::priority_queue <T>;
    template <class T> using mt = std::multiset <T>;
    template <class T> using ve = std::vector <T>;
    template <class T> using qu = std::queue <T>;
    typedef std::string str;
    typedef long double ld;
    typedef long long ll;
    typedef bool bo;
    typedef char ch;

    using namespace std;

    const ll inf = 1e18 + 18;
    const ll sz = 3e5 + 15;
    const ll md = 1e9 + 7;
    const ll mo = 998244353;
}

using namespace ddr;

const ll sm = 4e2 + 8;

bo dp[2][sm][sm];
str s;
ll k;

bo cac(ll tr, ll l, ll r, ll ac, ll bc) {
    if (l >= r) {
        return true;
    }

    if (k == ac) {
        // cout << "HI MF\n";
        return !(tr % 2);
    }

    if (k == bc) {
        // cout << "HI DF\n";
        return (tr % 2);
    }

    bo f = true;

    if (dp[tr % 2][l][r]) {
        return !dp[tr % 2][l][r];
    }

    if (tr % 2) {
        f &= cac(1 + tr, l + 1, r, ac + ('C' == s[l + 1]), bc);
        f &= cac(1 + tr, l, r - 1, ac + ('C' == s[r - 1]), bc);
    } else {
        f &= cac(1 + tr, l + 1, r, ac, bc + ('C' == s[l + 1]));
        f &= cac(1 + tr, l, r - 1, ac, bc + ('C' == s[r - 1]));
    }

    // for (ll i = 0; i < tr; i ++) {
    //     cout << '\t';
    // }

    // cout << f << '\n';

    return !(dp[tr % 2][l][r] = f);
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    ll n;
    cin >> n >> k >> s;

    bo lf = !cac(0, 0, n, 'C' == s[0], 0);
    // cout << '\n';
    bo rf = !cac(0, -1, n - 1, 'C' == s[n - 1], 0);

    cout << ((lf || rf) ? "DA" : "NE");
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -