Submission #494391

#	Time	Username	Problem	Language	Result	Execution time	Memory
494391		AlperenT	Kamenčići (COCI21_kamencici)	C++17	70 / 70	22 ms	22860 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 350 + 5;

int n, k, prefix[N], sum;

string str;

bool dp[N][N][N];

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

    cin >> n >> k;

    cin >> str;

    str = '$' + str;

    for(int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + (str[i] == 'C');

    for(int l = n; l >= 1; l--){
        for(int r = l; r <= n; r++){
            sum = prefix[n] - (prefix[r] - prefix[l - 1]);

            for(int i = 0; i < k; i++){
                int j = sum - i;

                if(j >= k) dp[l][r][i] = true;
                else{
                    if(!dp[l + 1][r][j] || !dp[l][r - 1][j]) dp[l][r][i] = true;
                    else dp[l][r][i] = false;
                }
            }
        }
    }

    cout << (dp[1][n][0] ? "DA" : "NE");
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40