Submission #508246

#	Time	Username	Problem	Language	Result	Execution time	Memory
508246		KoD	Kamenčići (COCI21_kamencici)	C++17	70 / 70	46 ms	85132 KiB

Main

#include <bits/stdc++.h>

using std::vector;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    int N, K;
    std::cin >> N >> K;
    vector<char> S(N);
    for (auto& x : S) {
        std::cin >> x;
    }
    vector<int> red(N + 1);
    for (int i = 0; i < N; ++i) {
        red[i + 1] = red[i] + (S[i] == 'C');
    }
    vector memo(N, vector(N + 1, vector<int>(K, -1)));
    std::cout << (RecLambda([&](auto&& dfs, const int l, const int r, const int k) -> int {
        if (k >= K) return 0;
        const int other = red[l] + (red[N] - red[r]) - k;
        if (other >= K) return 1;
        if (memo[l][r][k] != -1) return memo[l][r][k];
        if (dfs(l + 1, r, other) == 0) return memo[l][r][k] = 1;
        if (dfs(l, r - 1, other) == 0) return memo[l][r][k] = 1;
        return memo[l][r][k] = 0;
    })(0, N, 0) ? "DA" : "NE") << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40