제출 #1198005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198005		brover29	Kamenčići (COCI21_kamencici)	C++17	70 / 70	94 ms	172360 KiB

Main

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=355;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll n,dp[N][N][N],K,pref[N],suff[N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>K;
    string s;
    cin>>s;
    s=' '+s;
    for(ll i=1;i<=n;i++){
        pref[i]=pref[i-1]+(s[i]=='C');
    }for(ll i=n;i>=1;i--)suff[i]=pref[n]-pref[i-1];
    for(ll i=1;i<=n;i++){
        ll k=pref[i-1]+suff[i+1];
        for(ll k1=0;k1<=k;k1++){
            ll k2=k-k1;
            ll j=i-1+n-i;
            j%=2;
            if(j==0&&k2>=K)dp[i][i][k1]=1;
            if(j==0&&k1>=K)dp[i][i][k1]=0;
            if(j==1&&k1>=K)dp[i][i][k1]=1;
            if(j==1&&k2>=K)dp[i][i][k1]=0;

        }
    }

    for(ll len=2;len<=n;len++){
        for(ll l=1;l+len-1<=n;l++){
            ll r=l+len-1;
            ll k=pref[l-1]+suff[r+1];
            ll j=l-1+n-r;
            j%=2;
            for(ll k1=0;k1<=k;k1++){
                ll k2=k-k1;

                dp[l][r][k1]=!(dp[l+1][r][k1+(s[l]=='C')*(!j)]&&dp[l][r-1][k1+(s[r]=='C')*(!j)]);
//                if(l==1&&r==n&&k1==0){
//                    cout<<dp[l][r-1][k1+(s[r]=='C')*(!j)];
//                }
                if(j==0&&k2>=K)dp[l][r][k1]=1;
                if(j==0&&k1>=K)dp[l][r][k1]=0;
                if(j==1&&k1>=K)dp[l][r][k1]=1;
                if(j==1&&k2>=K)dp[l][r][k1]=0;
            }

        }
    }
    cout<<(dp[1][n][0] ? "DA" : "NE");
}

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