oj.uz

Submission #547248

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

const int maxn = 352;

int n, k;
int prefix_sum[maxn];
int dp[maxn][maxn][maxn] = {-1};


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;

    fill_n(&dp[0][0][0], 352 * 352 * 252, -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 74 ms 122448 KB Output is correct
2 Incorrect 63 ms 122480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 122448 KB Output is correct
2 Incorrect 63 ms 122480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 122448 KB Output is correct
2 Incorrect 63 ms 122480 KB Output isn't correct
3 Halted 0 ms 0 KB -