Submission #547247

#	Time	Username	Problem	Language	Result	Execution time	Memory
547247		MahfuzAhmed	Kamenčići (COCI21_kamencici)	C++14	0 / 70	81 ms	171020 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];


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;

    memset(dp, -1, sizeof dp);

    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