oj.uz

Submission #521507

# Submission time Handle Problem Language Result Execution time Memory
521507 2022-02-02T09:44:11 Z BadPenalty Kamenčići (COCI21_kamencici) C++14
70 / 70
 79 ms 182948 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<<"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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 182792 KB Output is correct
2 Correct 69 ms 182888 KB Output is correct
3 Correct 72 ms 182852 KB Output is correct
4 Correct 71 ms 182804 KB Output is correct
5 Correct 65 ms 182852 KB Output is correct
6 Correct 65 ms 182876 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 182792 KB Output is correct
2 Correct 69 ms 182888 KB Output is correct
3 Correct 72 ms 182852 KB Output is correct
4 Correct 71 ms 182804 KB Output is correct
5 Correct 65 ms 182852 KB Output is correct
6 Correct 65 ms 182876 KB Output is correct
7 Correct 64 ms 182928 KB Output is correct
8 Correct 65 ms 182856 KB Output is correct
9 Correct 66 ms 182880 KB Output is correct
10 Correct 71 ms 182844 KB Output is correct
11 Correct 66 ms 182948 KB Output is correct
12 Correct 65 ms 182860 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 182792 KB Output is correct
2 Correct 69 ms 182888 KB Output is correct
3 Correct 72 ms 182852 KB Output is correct
4 Correct 71 ms 182804 KB Output is correct
5 Correct 65 ms 182852 KB Output is correct
6 Correct 65 ms 182876 KB Output is correct
7 Correct 64 ms 182928 KB Output is correct
8 Correct 65 ms 182856 KB Output is correct
9 Correct 66 ms 182880 KB Output is correct
10 Correct 71 ms 182844 KB Output is correct
11 Correct 66 ms 182948 KB Output is correct
12 Correct 65 ms 182860 KB Output is correct
13 Correct 70 ms 182840 KB Output is correct
14 Correct 79 ms 182852 KB Output is correct
15 Correct 70 ms 182852 KB Output is correct
16 Correct 78 ms 182912 KB Output is correct
17 Correct 72 ms 182864 KB Output is correct
18 Correct 67 ms 182848 KB Output is correct