oj.uz

Submission #1108626

# Submission time Handle Problem Language Result Execution time Memory
1108626 2024-11-04T16:33:31 Z huantran Kamenčići (COCI21_kamencici) C++17
70 / 70
 39 ms 169688 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long int;
const int maxn = 351;
const int oo = 1e9 + 7;
const ll inf = 1e18;

int n, k, tol = 0;
int pre[maxn], dp[maxn][maxn][maxn];

int recursive(int l, int r, int m) {
    if (m >= k) {
        dp[l][r][m] = 0;
        return 0;
    }
        
    int h = tol - m - (pre[r] - pre[l - 1]);
    if (h >= k) {
        dp[l][r][m] = 1;
        return 1;
    }

    if (dp[l][r][m] != -1)
        return dp[l][r][m];

    dp[l][r][m] = (!recursive(l + 1, r, h) | !recursive(l, r - 1, h));
    return dp[l][r][m];
}

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

    cin >> n >> k;
    string s;
    cin >> s;
    s = ' ' + s;
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + (s[i] == 'C');
        if (s[i] == 'C')
            tol++;
    }

    for (int i = 0; i < maxn; i++) {
        for (int j = 0; j < maxn; j++) {
            for (int k = 0; k < maxn; k++)
                dp[i][j][k] = -1;
        }
    }

    if (recursive(1, n, 0))
        cout << "DA";
    else    
        cout << "NE";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 169552 KB Output is correct
2 Correct 20 ms 169552 KB Output is correct
3 Correct 20 ms 169564 KB Output is correct
4 Correct 19 ms 169504 KB Output is correct
5 Correct 18 ms 169652 KB Output is correct
6 Correct 21 ms 169548 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 169552 KB Output is correct
2 Correct 20 ms 169552 KB Output is correct
3 Correct 20 ms 169564 KB Output is correct
4 Correct 19 ms 169504 KB Output is correct
5 Correct 18 ms 169652 KB Output is correct
6 Correct 21 ms 169548 KB Output is correct
7 Correct 20 ms 169552 KB Output is correct
8 Correct 21 ms 169544 KB Output is correct
9 Correct 19 ms 169544 KB Output is correct
10 Correct 20 ms 169552 KB Output is correct
11 Correct 21 ms 169688 KB Output is correct
12 Correct 20 ms 169552 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 169552 KB Output is correct
2 Correct 20 ms 169552 KB Output is correct
3 Correct 20 ms 169564 KB Output is correct
4 Correct 19 ms 169504 KB Output is correct
5 Correct 18 ms 169652 KB Output is correct
6 Correct 21 ms 169548 KB Output is correct
7 Correct 20 ms 169552 KB Output is correct
8 Correct 21 ms 169544 KB Output is correct
9 Correct 19 ms 169544 KB Output is correct
10 Correct 20 ms 169552 KB Output is correct
11 Correct 21 ms 169688 KB Output is correct
12 Correct 20 ms 169552 KB Output is correct
13 Correct 19 ms 169552 KB Output is correct
14 Correct 39 ms 169552 KB Output is correct
15 Correct 22 ms 169552 KB Output is correct
16 Correct 35 ms 169568 KB Output is correct
17 Correct 27 ms 169552 KB Output is correct
18 Correct 24 ms 169552 KB Output is correct