제출 #647650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647650		GudStonks	Kamenčići (COCI21_kamencici)	C++17	70 / 70	53 ms	51044 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int n, k;
string s;
int dp[352][352][352], pr[352];

bool fun(int l = 0, int r = n - 1, int a = 0)
{
	int b = pr[l] + pr[n] - pr[r + 1] - a;
	if(dp[l][r][a] != 0)
		return dp[l][r][a] - 1;
    if(a == k || b == k)
        return b == k;
    if(!((n - (r - l + 1)) & 1))
    {
    	dp[l][r][a] = 1 + (fun(l + 1, r, a + (s[l] == 'C')) || fun(l, r - 1, a + (s[r] == 'C')));
        return dp[l][r][a] - 1;
    }
    else
    {
    	dp[l][r][a] = 1 + (fun(l + 1, r, a) && fun(l, r - 1, a));
        return dp[l][r][a] - 1;
    }
}
int main()
{
    cin>>n>>k;
    cin>>s;
    pr[0] = 0;
    for(int i = 1; i <= n; i++)
    {
    	pr[i] = pr[i - 1] + (s[i - 1] == 'C');
    }
    cout<<(fun() ? "DA" : "NE");
}

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