제출 #1324329

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

Main

#include <bits/stdc++.h>
using namespace std;
int n,k;
string s;
int memo[355][355][355];
int totored = 0;
int p[355];
bool solve(int l,int r,int k_me){
    int cur = 0;
    int rangered = p[r+1] - p[l];
    int taken = totored - rangered;
    int k_opp = taken - k_me;

    if(k_me >= k) return 0;
    if(k_opp >= k) return 1;

    if(memo[l][r][k_me] != 0){
        return memo[l][r][k_me] == 1;
    }
    bool win = 0;
    int new_red_l = k_me + (s[l] == 'C' ? 1 : 0);
    if(!solve(l+1,r,k_opp)){
        win = 1;
    }
    if(!win){
        int new_red_r = k_me + (s[r] == 'C' ? 1 : 0);
        if(!solve(l,r-1,k_opp)){
            win = 1;
        }
    }
    memo[l][r][k_me] = win ? 1 : 2;
    return win;
}

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

    cin >> n >> k;
    cin >> s;

    totored = 0;
    p[0] = 0;
    for(int i = 0 ; i < n ; i++)   {
        if(s[i] == 'C') totored++;
        p[i+1] = p[i] + (s[i] == 'C' ? 1 : 0); 
    }
    memset(memo,0,sizeof(memo));
    cout << (solve(0,n-1,0) ? "DA" : "NE");
}

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