oj.uz

Submission #862119

# Submission time Handle Problem Language Result Execution time Memory
862119 2023-10-17T14:20:48 Z Youssif_Elkadi Kamenčići (COCI21_kamencici) C++17
70 / 70
 99 ms 336208 KB 
#include <bits/stdc++.h>
using namespace std;
const long long N = 350, mod = 1e9 + 7, base = 31;
int dp[N][N][N][2];
int n, k;
string x;
int solve(int l, int r, int rem1, int rem2, int t)
{
    if (rem1 == 0)
        return 0;
    if (rem2 == 0)
        return 1;
    if (~dp[l][r][rem1][t])
        return dp[l][r][rem1][t];
    if (t)
        return dp[l][r][rem1][t] = min(solve(l + 1, r, rem1, rem2 - (x[l] == 'C'), 0), solve(l, r - 1, rem1, rem2 - (x[r] == 'C'), 0));
    else
        return dp[l][r][rem1][t] = max(solve(l + 1, r, rem1 - (x[l] == 'C'), rem2, 1), solve(l, r - 1, rem1 - (x[r] == 'C'), rem2, 1));
}
int main()
{
    memset(dp, -1, sizeof dp);
    cin >> n >> k;
    cin >> x;
    cout << (solve(0, n - 1, k, k, 0) ? "DA" : "NE");
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 335900 KB Output is correct
2 Correct 77 ms 335956 KB Output is correct
3 Correct 75 ms 335952 KB Output is correct
4 Correct 81 ms 336208 KB Output is correct
5 Correct 74 ms 335956 KB Output is correct
6 Correct 75 ms 335888 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 335900 KB Output is correct
2 Correct 77 ms 335956 KB Output is correct
3 Correct 75 ms 335952 KB Output is correct
4 Correct 81 ms 336208 KB Output is correct
5 Correct 74 ms 335956 KB Output is correct
6 Correct 75 ms 335888 KB Output is correct
7 Correct 74 ms 336028 KB Output is correct
8 Correct 79 ms 335916 KB Output is correct
9 Correct 78 ms 335860 KB Output is correct
10 Correct 75 ms 335972 KB Output is correct
11 Correct 76 ms 335956 KB Output is correct
12 Correct 75 ms 335932 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 335900 KB Output is correct
2 Correct 77 ms 335956 KB Output is correct
3 Correct 75 ms 335952 KB Output is correct
4 Correct 81 ms 336208 KB Output is correct
5 Correct 74 ms 335956 KB Output is correct
6 Correct 75 ms 335888 KB Output is correct
7 Correct 74 ms 336028 KB Output is correct
8 Correct 79 ms 335916 KB Output is correct
9 Correct 78 ms 335860 KB Output is correct
10 Correct 75 ms 335972 KB Output is correct
11 Correct 76 ms 335956 KB Output is correct
12 Correct 75 ms 335932 KB Output is correct
13 Correct 74 ms 335956 KB Output is correct
14 Correct 99 ms 336100 KB Output is correct
15 Correct 78 ms 335980 KB Output is correct
16 Correct 91 ms 335956 KB Output is correct
17 Correct 86 ms 335956 KB Output is correct
18 Correct 78 ms 335864 KB Output is correct