oj.uz

Submission #1004699

# Submission time Handle Problem Language Result Execution time Memory
1004699 2024-06-21T12:51:25 Z atom Kamenčići (COCI21_kamencici) C++17
70 / 70
 33 ms 171160 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 Atakes, int l, int r) {
    if (dp[Atakes][l][r] != -1) return dp[Atakes][l][r];
    
    int remains = prf[r] - prf[l - 1];
    int Btakes = prf[n] - remains - Atakes;

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

    int ans = 0;
    if (l + 1 <= r && solve(Btakes, l + 1, r) == 0) 
        ans = 1;
    if (r - 1 >= l && solve(Btakes, l, r - 1) == 0) 
        ans = 1;

    return dp[Atakes][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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 171100 KB Output is correct
2 Correct 24 ms 171096 KB Output is correct
3 Correct 20 ms 171100 KB Output is correct
4 Correct 20 ms 171100 KB Output is correct
5 Correct 23 ms 170952 KB Output is correct
6 Correct 22 ms 171160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 171100 KB Output is correct
2 Correct 24 ms 171096 KB Output is correct
3 Correct 20 ms 171100 KB Output is correct
4 Correct 20 ms 171100 KB Output is correct
5 Correct 23 ms 170952 KB Output is correct
6 Correct 22 ms 171160 KB Output is correct
7 Correct 22 ms 170960 KB Output is correct
8 Correct 22 ms 171096 KB Output is correct
9 Correct 22 ms 171100 KB Output is correct
10 Correct 23 ms 171072 KB Output is correct
11 Correct 22 ms 171088 KB Output is correct
12 Correct 23 ms 171100 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 171100 KB Output is correct
2 Correct 24 ms 171096 KB Output is correct
3 Correct 20 ms 171100 KB Output is correct
4 Correct 20 ms 171100 KB Output is correct
5 Correct 23 ms 170952 KB Output is correct
6 Correct 22 ms 171160 KB Output is correct
7 Correct 22 ms 170960 KB Output is correct
8 Correct 22 ms 171096 KB Output is correct
9 Correct 22 ms 171100 KB Output is correct
10 Correct 23 ms 171072 KB Output is correct
11 Correct 22 ms 171088 KB Output is correct
12 Correct 23 ms 171100 KB Output is correct
13 Correct 22 ms 170892 KB Output is correct
14 Correct 33 ms 170928 KB Output is correct
15 Correct 24 ms 171100 KB Output is correct
16 Correct 33 ms 171092 KB Output is correct
17 Correct 27 ms 171100 KB Output is correct
18 Correct 23 ms 171100 KB Output is correct