Submission #521507

#	Time	Username	Problem	Language	Result	Execution time	Memory
521507		BadPenalty	Kamenčići (COCI21_kamencici)	C++14	70 / 70	79 ms	182948 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define yes cout<<"DA"<<endl
#define no cout<<"NE"<<endl
const int N = 360,mod = 1e9+7;
int n,k;
int dp[N][N][N];
int num[N];
bool check(int l,int r,int m)
{
    if(dp[l][r][m]!=-1)
        return dp[l][r][m];
    int total = num[n-1];
    int curr = num[r];
    if(l)
        curr-=num[l-1];
    int other = total - (m+curr) ;
    if(m>=k)
        dp[l][r][m] = 0;
    else if(other>=k)
        dp[l][r][m] = 1;
    else
    {
        if(check(l+1,r,other)==0||check(l,r-1,other)==0)
            dp[l][r][m] = 1;
        else
            dp[l][r][m] = 0;
    }
    return dp[l][r][m];
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    string s;
    cin>>s;
    for(int i = 0;i<N;i++)for(int j = 0;j<N;j++)for(int g = 0;g<N;g++)
        dp[i][j][g] = -1;
    for(int i = 0;i<n;i++)
    {
        num[i]+= (s[i]=='C') ;
        if(i)
            num[i]+=num[i-1];
    }
    if(check(0,n-1,0))
        yes;
    else no;
    return 0;
}
/*

*/

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