Submission #508246

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
508246	2022-01-13 07:47:34	KoD	Kamenčići (COCI21_kamencici)	C++17	70 / 70	46 ms	85132 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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