oj.uz

Submission #743129

# Submission time Handle Problem Language Result Execution time Memory
743129 2023-05-17T08:15:18 Z sword060 Kamenčići (COCI21_kamencici) C++17
0 / 70
 81 ms 175392 KB 
#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);
	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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 175392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 175392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 175392 KB Output isn't correct
2 Halted 0 ms 0 KB -