제출 #638457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638457		NotLinux	Kamenčići (COCI21_kamencici)	C++14	10 / 70	1 ms	1364 KiB

Main

/**
 * author: NotLinux
 * created: 06.09.2022 ~ 09:33:06
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
    #include "/home/notlinux/debug.h"
#else
    #define debug(x...) void(37)
#endif
int n,k;string str;
vector<vector<vector<int>>>dp;
vector<int>pre,suff;
//1 = ben yendim , 0 = o yendi
int func(int l,int r,int z){
    if(dp[l][r][z]!=-1)return dp[l][r][z];
    int toplam=pre[l]+suff[n-r-1];
    if((toplam-z)==k){
        dp[l][r][z] = 1;
        return dp[l][r][z];
    }
    else if(z == k){
        dp[l][r][z] = 0;
        return dp[l][r][z];   
    }
    int p1,p2;
    if((l+r)%2==0){
        p1=func(l+1,r,z+(str[l]=='C'));
        p2=func(l,r+1,z+(str[n-r-1]=='C'));
    }
    else {
        p1=func(l+1,r,z);
        p2=func(l,r+1,z);
    }
    if((l+r)%2==0){
        dp[l][r][z] = p1|p2;
    }
    else {
        dp[l][r][z] = p1&p2;
    }
    return dp[l][r][z];
}
void solve(){
    cin>>n>>k>>str;
    dp.assign(n,vector<vector<int>>(n,vector<int>(n,-1)));
    pre.resize(n+1);suff.resize(n+1);
    for(int i=0;i<n;i++)pre[i+1]=pre[i]+(str[i]=='C');
    for(int i=n-1;i>0;i--)suff[i-1]=suff[i]+(str[i-1]=='C');
    cout<<(func(0,0,0)?"DA":"NE")<<endl;    
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    int tt=1;
    //cin >> tt;
    while(tt--)solve();
}

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