oj.uz

Submission #521859

# Submission time Handle Problem Language Result Execution time Memory
521859 2022-02-03T10:16:54 Z BadPenalty Kamenčići (COCI21_kamencici) C++14
10 / 70
 1 ms 972 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Incorrect 1 ms 844 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Incorrect 1 ms 844 KB Output isn't correct
11 Halted 0 ms 0 KB -