제출 #703673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703673		Pacybwoah	Kamenčići (COCI21_kamencici)	C++14	70 / 70	107 ms	175348 KiB

Main

//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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40