제출 #1206965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206965		Fatonim	Kamenčići (COCI21_kamencici)	C++20	70 / 70	168 ms	344740 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#ifdef ONPC
#include "debug.h"
#else
#define dbg(...)
#endif

#define ll long long
#define int long long
#define ld long double
#define pi pair<int, int>
#define sz(a) ((int)(a.size()))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sqr(n) ((n) * (n))
#define divup(a, b) (((a) + (b)-1) / (b))
#define popcount(n) __builtin_popcountll(n)
#define clz(n) __builtin_clzll(n)
#define Fixed(a) cout << fixed << setprecision(12) << a;

template <class T> bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool chmax(T& a, const T& b) { return b > a ? a = b, 1 : 0; }

const int mod = 998244353; // 998244353 1e9 + 7
const ll inf = (ll)(1e18) + 7;
const ld eps = 1e-9;

const int B = 32;
const int N = 350 + 3;
const int logn = 20;
const int maxn = 2e5 + 7;
/////////////////////////solve/////////////////////////

int dp[N][N][N];
int k, n;
string s;

int rec(int cur, int l, int r, int c0, int c1) {
    int& res = dp[l][r][c0];
    if (res == -1) {
        res = 0;
        if (cur == 0) {
            int nc = c0 + (s[l] == 'C');
            if (nc < k) res |= rec(cur ^ 1, l + 1, r, nc, c1) ^ 1;
            nc = c0 + (s[r] == 'C');
            if (nc < k) res |= rec(cur ^ 1, l, r - 1, nc, c1) ^ 1;
        }
        else {
            int nc = c1 + (s[l] == 'C');
            if (nc < k) res |= rec(cur ^ 1, l + 1, r, c0, nc) ^ 1;
            nc = c1 + (s[r] == 'C');
            if (nc < k) res |= rec(cur ^ 1, l, r - 1, c0, nc) ^ 1;
        }
    }
    return res;
}

void solve() {
    cin >> n >> k;
    cin >> s;

    memset(dp, -1, sizeof(dp));
    int ans = rec(0, 0, n - 1, 0, 0);
    cout << (ans ? "DA" : "NE");
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ONPC
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    solve();
}

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