제출 #1178679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178679		vannn168	Kamenčići (COCI21_kamencici)	C++20	70 / 70	87 ms	171844 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 355;
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';
}
// case for taking s[l] (l, r) -> p[n] - p[r] + p[l] - mine - ()

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