제출 #547251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
547251		MahfuzAhmed	Kamenčići (COCI21_kamencici)	C++14	70 / 70	58 ms	122548 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][v];
 
    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;
 
    fill_n(&dp[0][0][0], 352 * 352 * 252, -1);
 
    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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40