oj.uz

Submission #1004698

# Submission time Handle Problem Language Result Execution time Memory
1004698 2024-06-21T12:48:21 Z atom Kamenčići (COCI21_kamencici) C++17
0 / 70
 22 ms 171100 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 171100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 171100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 171100 KB Output isn't correct
2 Halted 0 ms 0 KB -