oj.uz

Submission #547249

# Submission time Handle Problem Language Result Execution time Memory
547249 2022-04-10T04:52:45 Z MahfuzAhmed Kamenčići (COCI21_kamencici) C++14
0 / 70
 72 ms 171020 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 352;

int n, k;
int prefix_sum[maxn];
int dp[maxn][maxn][maxn];


int get_ans(int l, int r, int v){
    int& res = dp[l][r][k];

    if(res == -1){
        int red = prefix_sum[n - 1];
        int left = prefix_sum[r];
        if(l) left -= prefix_sum[l - 1];

        int other = red - left - v;

        if(v >= k)
            res = 0;
        else if(other >= k)
            res = 1;
        else
            if(!get_ans(l + 1, r, other) || !get_ans(l, r - 1, other))
                res = 1;
            else
                res = 0;
    }

    return res;
}


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

    cin >> n >> k;
    string str; cin >> str;

    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;
 
    prefix_sum[0] = (str[0] == 'C');
    for(int i = 1; i < n; i++)
        prefix_sum[i] = prefix_sum[i - 1] + (str[i] == 'C');

    if(get_ans(0, n -1, 0))
        cout << "DA\n";
    else
        cout << "NE\n";


    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 170956 KB Output is correct
2 Incorrect 64 ms 171020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 170956 KB Output is correct
2 Incorrect 64 ms 171020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 170956 KB Output is correct
2 Incorrect 64 ms 171020 KB Output isn't correct
3 Halted 0 ms 0 KB -