Submission #900162

#TimeUsernameProblemLanguageResultExecution timeMemory
900162mariaclaraKamenčići (COCI21_kamencici)C++17
70 / 70
26 ms41816 KiB
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
#define all(x) x.begin(), x.end()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, k, prefix[500], sufix[500];
string s;
bool dp[350][350][350]; // l, r, C pegos

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

    cin >> n >> k >> s;
    
    for(int i = 1; i <= n; i++)
        prefix[i] = prefix[i-1] + (s[i-1] == 'C');

    for(int i = 1; i <= n; i++)
        sufix[i] = prefix[n] - prefix[i-1];

    for(int tam = 1; tam <= n; tam++) { // tamanho do intervalo
        for(int l = 0; l + tam <= n; l++) {
            int r = l+tam-1;

            for(int C = 0; C < k; C++) { // quantos eu coletei até agr
                if(l == r) {
                    dp[l][r][C] = C+1 < k;
                    continue;
                }

                // dp[l+1][r]
                int a = prefix[l] + sufix[r+2] - C;
                if(a >= 0 and dp[l+1][r][a] == 0) dp[l][r][C] = 1;
                // dp[l][r-1]
                if(a >= 0 and dp[l][r-1][a] == 0) dp[l][r][C] = 1;

                //cout << "[ " << l << ", " << r << ", " << C << ", " << a << ", " << b << " ] = " << dp[l][r][C] << "\n";
            }
        }
    } 

    if(dp[0][n-1][0]) cout << "DA\n";
    else cout << "NE\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...