oj.uz

Submission #743134

# Submission time Handle Problem Language Result Execution time Memory
743134 2023-05-17T08:17:01 Z sword060 Kamenčići (COCI21_kamencici) C++17
70 / 70
 92 ms 175496 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)-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

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

# Verdict Execution time Memory Grader output
1 Correct 69 ms 175364 KB Output is correct
2 Correct 72 ms 175384 KB Output is correct
3 Correct 71 ms 175324 KB Output is correct
4 Correct 79 ms 175376 KB Output is correct
5 Correct 71 ms 175408 KB Output is correct
6 Correct 68 ms 175372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 175364 KB Output is correct
2 Correct 72 ms 175384 KB Output is correct
3 Correct 71 ms 175324 KB Output is correct
4 Correct 79 ms 175376 KB Output is correct
5 Correct 71 ms 175408 KB Output is correct
6 Correct 68 ms 175372 KB Output is correct
7 Correct 67 ms 175296 KB Output is correct
8 Correct 69 ms 175384 KB Output is correct
9 Correct 68 ms 175384 KB Output is correct
10 Correct 70 ms 175324 KB Output is correct
11 Correct 72 ms 175364 KB Output is correct
12 Correct 72 ms 175400 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 175364 KB Output is correct
2 Correct 72 ms 175384 KB Output is correct
3 Correct 71 ms 175324 KB Output is correct
4 Correct 79 ms 175376 KB Output is correct
5 Correct 71 ms 175408 KB Output is correct
6 Correct 68 ms 175372 KB Output is correct
7 Correct 67 ms 175296 KB Output is correct
8 Correct 69 ms 175384 KB Output is correct
9 Correct 68 ms 175384 KB Output is correct
10 Correct 70 ms 175324 KB Output is correct
11 Correct 72 ms 175364 KB Output is correct
12 Correct 72 ms 175400 KB Output is correct
13 Correct 70 ms 175496 KB Output is correct
14 Correct 92 ms 175328 KB Output is correct
15 Correct 76 ms 175308 KB Output is correct
16 Correct 90 ms 175392 KB Output is correct
17 Correct 89 ms 175340 KB Output is correct
18 Correct 69 ms 175452 KB Output is correct