oj.uz

Submission #703673

# Submission time Handle Problem Language Result Execution time Memory
703673 2023-02-28T05:55:53 Z Pacybwoah Kamenčići (COCI21_kamencici) C++14
70 / 70
 107 ms 175348 KB 
//upsolve
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    vector<int> pre(n+1);
    for(int i=1;i<=n;i++){
        if(s[i-1]=='C') pre[i]=pre[i-1]+1;
        else pre[i]=pre[i-1];
    }
    vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(n+1,vector<int>(pre[n]+1)));
    for(int i=1;i<=n;i++){
        for(int j=0;j<=pre[n];j++){
            if(j+(s[i-1]=='C')>=k) dp[i][i][j]=0;
            else dp[i][i][j]=1;
        }
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j+i-1<=n;j++){
            for(int l=0;l<=pre[n]-(pre[j+i-1]-pre[j-1]);l++){
                int bcnt=pre[n]-(pre[j+i-1]-pre[j-1])-l;
                if(l>=k) dp[j][j+i-1][l]=0;
                else if(bcnt>=k) dp[j][j+i-1][l]=1;
                else if(dp[j+1][j+i-1][bcnt]&&dp[j][j+i-2][bcnt]) dp[j][j+i-1][l]=0;
                else dp[j][j+i-1][l]=1;
            }
        }
    }
    if(dp[1][n][0]) cout<<"DA\n";
    else cout<<"NE\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 1 ms 944 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 808 KB Output is correct
12 Correct 1 ms 724 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 1 ms 944 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 808 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 107 ms 175348 KB Output is correct
14 Correct 32 ms 43476 KB Output is correct
15 Correct 25 ms 34260 KB Output is correct
16 Correct 86 ms 132448 KB Output is correct
17 Correct 102 ms 167616 KB Output is correct
18 Correct 97 ms 164756 KB Output is correct