Submission #864834

#	Time	Username	Problem	Language	Result	Execution time	Memory
864834		epicci23	Kamenčići (COCI21_kamencici)	C++17	70 / 70	59 ms	350800 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) ((int)(x).size())


int ar[355];
int dp[355][355][355];
int pre[355];
int suf[355];
int n,k;

int f(int l,int r,int c){

  int u = (l-1+n-r)&1;
  int c2 = pre[l-1] + suf[r+1] - c;
  
  if(c==k) return 0; 
  if(c2==k) return 1;
  if(dp[l][r][c]!=-1) return dp[l][r][c];
   
  int b=0,s=0;

  if(f(l+1,r,c+(u==0 && ar[l]))) b=1;
  else s=1;

  if(f(l,r-1,c+(u==0 && ar[r]))) b=1;
  else s=1;

  if(!u){
    if(b) return dp[l][r][c]=1;
    return dp[l][r][c]=0;
  }

  if(s) return dp[l][r][c]=0;
  return dp[l][r][c]=1;
}

void solve(){

 memset(dp,-1,sizeof(dp));

 cin >> n >> k;
 string s;
 cin >> s;
 
 for(int i=1;i<=n;i++) ar[i]=(s[i-1]=='C');

 pre[0]=0;
 for(int i=1;i<=n;i++) pre[i]=pre[i-1]+ar[i];

 suf[n+1]=0;
 for(int i=n;i>=1;i--) suf[i]=suf[i+1]+ar[i];
  
 int xd = f(1,n,0);
 
 if(xd) cout << "DA\n";
 else cout << "NE\n";

}


int32_t main(){

  ios::sync_with_stdio(0);
  cin.tie(0);

  int t=1;//cin >> t;
  while(t--) solve();
}

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