Submission #547248

#	Time	Username	Problem	Language	Result	Execution time	Memory
547248		MahfuzAhmed	Kamenčići (COCI21_kamencici)	C++14	0 / 70	74 ms	122480 KiB

Main

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40