Submission #743134

#	Time	Username	Problem	Language	Result	Execution time	Memory
743134		sword060	Kamenčići (COCI21_kamencici)	C++17	70 / 70	92 ms	175496 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 355;
int x,k,pre[N],dp[N][N][N];
string s;
int get(int l,int r){
	return pre[r]-pre[l-1];
}
int rec(int l,int r,int a){
	int b=get(0,l-1)+get(r+1,x)-a;
	if(a>=k||b>=k)return (b>=k);
	if(~dp[l][r][a])return dp[l][r][a];
	int c1=0,c2=0,z1=get(l,l),z2=get(r,r);
	if(a+z1<k)c1|=(rec(l+1,r-1,a+z1)&rec(l+2,r,a+z1));
	if(a+z2<k)c2|=(rec(l+1,r-1,a+z2)&rec(l,r-2,a+z2));
	return dp[l][r][a]=(c1|c2);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>x>>k>>s;
	s='#'+s;
	for(int i=1;i<=x;i++)pre[i]=pre[i-1]+(s[i]=='C');
	pre[x+1]=pre[x];
	memset(dp,-1,sizeof(dp));
	cout<<(rec(1,x,0)?"DA":"NE");
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int rec(int, int, int)':
Main.cpp:7:23: warning: array subscript -1 is below array bounds of 'int [355]' [-Warray-bounds]
    7 |  return pre[r]-pre[l-1];
      |                ~~~~~~~^
Main.cpp:4:9: note: while referencing 'pre'
    4 | int x,k,pre[N],dp[N][N][N];
      |         ^~~

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