oj.uz

Submission #497124

# Submission time Handle Problem Language Result Execution time Memory
497124 2021-12-22T13:27:46 Z Abrar_Al_Samit Kamenčići (COCI21_kamencici) C++17
70 / 70
 88 ms 85260 KB 
#include<bits/stdc++.h>
using namespace std;

const int MX = 355;
int n, k;
string s; 
int pre[MX], suf[MX];
int getRed(int l, int r) {
	return pre[l-1] + suf[r+1];
}
bool vis[MX][MX][MX][2], dp[MX][MX][MX][2];
bool solve(int l, int r, int red, int who) {
	bool &ret = dp[l][r][red][who];
	if(vis[l][r][red][who]) return ret;
	vis[l][r][red][who] = 1;
	int oppred = getRed(l, r)-red;
	if(s[l]!='C' || red+1<k) ret |= solve(l+1, r, oppred, who^1)==0;
	if(s[r]!='C' || red+1<k) ret |= solve(l, r-1, oppred, who^1)==0;
	return ret;
}
void PlayGround() {
	cin >> n >> k;
	cin >> s;
	s = "#" + s;
	for(int i=1; i<=n; ++i) {
		pre[i] = pre[i-1] + (s[i]=='C');
	}
	for(int i=n; i; --i) {
		suf[i] = suf[i+1] + (s[i]=='C');
	}
	if(solve(1, n, 0, 1)) cout << "DA\n";
	else cout << "NE\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 1212 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1996 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 1212 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1996 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 88 ms 81600 KB Output is correct
15 Correct 19 ms 26692 KB Output is correct
16 Correct 48 ms 51296 KB Output is correct
17 Correct 53 ms 85260 KB Output is correct
18 Correct 21 ms 33740 KB Output is correct