Submission #1178534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178534		vannn168	Kamenčići (COCI21_kamencici)	C++20	30 / 70	43 ms	111360 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int dp[N][N][N], p[N];
string s;
int n, k;
int rec(int l, int r, int cnt) {
    if(l > r) return 0;
    if(dp[l][r][cnt] != -1) return dp[l][r][cnt];
    dp[l][r][cnt] = 0;
    if(cnt + (s[l] == 'C') < k) dp[l][r][cnt] |= !rec(l + 1, r, p[n] - p[r] + p[l] - cnt - (s[l] == 'C'));
    if(cnt + (s[r] == 'C') < k) dp[l][r][cnt] |= !rec(l, r - 1, p[n] - p[r - 1] + p[l - 1] - cnt - (s[r] == 'C'));
    return dp[l][r][cnt];
}
int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k >> s; 
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            for(int p = 0; p <= n; ++p) {
                dp[i][j][p] = -1;
            }
        }
    }
    s = ' ' + s;
    for(int i = 0; i < n; ++i) {
        p[i + 1] = p[i] + (s[i + 1] == 'C');
    }
    cout << (rec(1, n, 0) ? "DA" : "NE") << '\n';
}

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