oj.uz

Submission #988693

# Submission time Handle Problem Language Result Execution time Memory
988693 2024-05-25T14:58:40 Z coolboy19521 Kamenčići (COCI21_kamencici) C++17
70 / 70
 13 ms 15960 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[sm][sm][sm];
ll pr[sm];
ll n, k;

bo cac(ll le, ll ri, ll co) {
    if (dp[le][ri][co]) {
        return dp[le][ri][co];
    }

    ll igo = pr[ri];

    if (le) {
        igo -= pr[le - 1];
    }

    ll oco = pr[n - 1] - igo - co;

    if (co >= k) {
        return 0;
    } else if (oco >= k) {
        return 1;
    }

    return dp[le][ri][co] = !cac(le + 1, ri, oco) || !cac(le, ri - 1, oco);
}

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

    str s;
    cin >> n >> k >> s;

    pr[0] = 'C' == s[0];

    for (ll i = 1; i < n; i ++) {
        pr[i] = pr[i - 1] + ('C' == s[i]);
    }

    cout << (cac(0, n - 1, 0) ? "DA" : "NE");
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 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 604 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 856 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 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 604 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 13 ms 15960 KB Output is correct
15 Correct 5 ms 5980 KB Output is correct
16 Correct 11 ms 14684 KB Output is correct
17 Correct 10 ms 15608 KB Output is correct
18 Correct 4 ms 7260 KB Output is correct