Submission #752326

#	Time	Username	Problem	Language	Result	Execution time	Memory
752326		Augustyn	Kamenčići (COCI21_kamencici)	C++17	70 / 70	93 ms	85156 KiB

Main

#include<iostream>
#include<string>
using namespace std;
int n,k;
int dp[351][351][351];
string kam;
int Czy_zn_C(int t)
{
    return kam[t]=='C';
}
int wejdz(int l, int p, int ilemaB)
{
    if(dp[l][p][ilemaB]!=0)
        return dp[l][p][ilemaB];
    if(ilemaB==0)
    {
        dp[l][p][ilemaB]=1;
        return dp[l][p][ilemaB];
    }
    if(l==p)
    {
        if(n%2==0)
        {
            dp[l][p][ilemaB]=1;
        }
        else
        {
            if(kam[l]=='C')
                dp[l][p][ilemaB]=2;
            else
                dp[l][p][ilemaB]=1;
        }
    }
    else
    {
        dp[l][p][ilemaB]=10000;
        if((n-(p-l+1))%2==0)
        {
            //Ruch A
            dp[l][p][ilemaB]=min(wejdz(l+1,p,ilemaB)+Czy_zn_C(l),
                                 wejdz(l,p-1,ilemaB)+Czy_zn_C(p));
        }
        else
        {
            //Ruch B
            dp[l][p][ilemaB]=max(wejdz(l+1,p,ilemaB-Czy_zn_C(l)),
                                 wejdz(l,p-1,ilemaB-Czy_zn_C(p)));
        }
    }
    return dp[l][p][ilemaB];
}
int main()
{
    cin>>n>>k;
    cin>>kam;
    if(wejdz(0,n-1,k)>k)
        printf("NE");
    else
        printf("DA");
    return 0;
}

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