Submission #521859

#	Time	Username	Problem	Language	Result	Execution time	Memory
521859		BadPenalty	Kamenčići (COCI21_kamencici)	C++14	10 / 70	1 ms	972 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<<"Yes"<<endl
#define no cout<<"No"<<endl
const int N = 410,mod = 1e9+7;

int dp[N][N];
int n,k;
string s;
bool solve(int l = 0,int r = n-1,int k1 = 0,int k2 = 0,int i = 1)
{
    int &res = dp[l][r];
    if(res!=-1)
        return res;

    if(k2>=k)
        res = 1;
    else if(k1>=k)
        res = 0;
    else
    {
        if(i == 1)
        {
            if(s[l]=='C')
                dp[l+1][r] = solve(l+1,r,k1+1,k2,i+1);
            else
                dp[l+1][r] = solve(l+1,r,k1,k2,i+1);

            if(s[r]=='C')
                dp[l][r-1] = solve(l,r-1,k1+1,k2,i+1);
            else
                dp[l][r-1] = solve(l,r-1,k1,k2,i+1);
        }
        else
        {
            if(s[l]=='C')
                dp[l+1][r] = solve(l+1,r,k1,k2+1,i-1);
            else
                dp[l+1][r] = solve(l+1,r,k1,k2,i-1);
            if(s[r]=='C')
                dp[l][r-1] = solve(l,r-1,k1,k2+1,i-1);
            else
                dp[l][r-1] = solve(l,r-1,k1,k2,i-1);
        }
        if(i==2)
        {
            if(dp[l+1][r]==1&&dp[l][r-1]==1)
                res  = 1;
            else res = 0;
        }
        else
        {
            if(dp[l+1][r]==1||dp[l][r-1]==1)
                res  = 1;
            else res = 0;
        }

    }
    //cout<<l<<' '<<r<<' '<<res<<' '<<i<<endl;
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k>>s;
    for(int i = 0;i<N;i++)for(int j = 0;j<N;j++)
        dp[i][j] = -1;
    solve();
    if(dp[0][n-1])
        cout<<"DA"<<endl;
    else cout<<"NE"<<endl;
    return 0;
}
/*

*/

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