Submission #1004698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004698		atom	Kamenčići (COCI21_kamencici)	C++17	0 / 70	22 ms	171100 KiB

Main

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
 
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
 
const int N = 352;
int dp[N][N][N];
int prf[N];
int n, k;
string s;

// A takes cnt,
int solve(int cnt, int l, int r) {
    if (dp[cnt][l][r] != -1) return dp[cnt][l][r];
    
    int remains = prf[r] - prf[l - 1];
    int Btakes = prf[n] - remains - cnt;

    if (cnt >= k) return 0;
    else if (Btakes >= k) return 1;

    int ans = 0;
    if (l + 1 <= r && solve(cnt + (s[l] == 'C'), l + 1, r) == 0) 
        ans = 1;
    if (r - 1 >= l && solve(cnt + (s[r] == 'C'), l, r - 1) == 0) 
        ans = 1;

    return dp[cnt][l][r] = ans;
}

// 1: last position of x, -1: second-last position of x -> sum(l, r) = 0-> non-unique subarray, > 0: unique
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    cin >> n >> k;
    cin >> s;

    s = "@" + s;
    for (int i = 1; i <= n; ++i)
        prf[i] = prf[i - 1] + (s[i] == 'C');

    memset(dp, -1, sizeof dp);
    cout << (solve(0, 1, n)? "DA\n" : "NE\n");
    return 0;
}

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