oj.uz

Submission #890624

# Submission time Handle Problem Language Result Execution time Memory
890624 2023-12-21T16:51:54 Z serifefedartar Kamenčići (COCI21_kamencici) C++17
70 / 70
 46 ms 183164 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 998244353
#define LOGN 21
#define MAXN 360

int n, k, dp[MAXN][MAXN][MAXN], pref[MAXN];
string s;
bool solve(int l, int r, int K) {
	if (dp[l][r][K] != -1)
		return dp[l][r][K];
	if (K >= k)
		return dp[l][r][K] = 0;
	if (pref[n] - pref[r] + pref[l-1] - K >= k)
		return dp[l][r][K] = 1;

	if ((n - (r - l + 1)) % 2)
		return dp[l][r][K] = solve(l+1, r, K) && solve(l, r-1, K);
	return dp[l][r][K] = solve(l+1, r, K + (s[l] == 'C')) || solve(l, r-1, K + (s[r] == 'C'));
}

int main() {
	fast
	memset(dp, -1, sizeof(dp));
	cin >> n >> k >> s;
	s = "#" + s;

	for (int i = 1; i <= n; i++)
		pref[i] = pref[i-1] + (s[i] == 'C');
	if (solve(1, n, 0))
		cout << "DA\n";
	else
		cout << "NE\n";
}

Compilation message

Main.cpp: In function 'bool solve(int, int, int)':
Main.cpp:18:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   18 |   return dp[l][r][K] = 0;
      |          ~~~~~~~~~~~~^~~
Main.cpp:20:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   20 |   return dp[l][r][K] = 1;
      |          ~~~~~~~~~~~~^~~
Main.cpp:23:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   23 |   return dp[l][r][K] = solve(l+1, r, K) && solve(l, r-1, K);
      |          ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:24:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   24 |  return dp[l][r][K] = solve(l+1, r, K + (s[l] == 'C')) || solve(l, r-1, K + (s[r] == 'C'));
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 183104 KB Output is correct
2 Correct 22 ms 182864 KB Output is correct
3 Correct 22 ms 182872 KB Output is correct
4 Correct 23 ms 183164 KB Output is correct
5 Correct 21 ms 182876 KB Output is correct
6 Correct 21 ms 182864 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 183104 KB Output is correct
2 Correct 22 ms 182864 KB Output is correct
3 Correct 22 ms 182872 KB Output is correct
4 Correct 23 ms 183164 KB Output is correct
5 Correct 21 ms 182876 KB Output is correct
6 Correct 21 ms 182864 KB Output is correct
7 Correct 22 ms 182968 KB Output is correct
8 Correct 22 ms 182864 KB Output is correct
9 Correct 20 ms 182872 KB Output is correct
10 Correct 21 ms 182976 KB Output is correct
11 Correct 22 ms 182876 KB Output is correct
12 Correct 21 ms 182876 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 183104 KB Output is correct
2 Correct 22 ms 182864 KB Output is correct
3 Correct 22 ms 182872 KB Output is correct
4 Correct 23 ms 183164 KB Output is correct
5 Correct 21 ms 182876 KB Output is correct
6 Correct 21 ms 182864 KB Output is correct
7 Correct 22 ms 182968 KB Output is correct
8 Correct 22 ms 182864 KB Output is correct
9 Correct 20 ms 182872 KB Output is correct
10 Correct 21 ms 182976 KB Output is correct
11 Correct 22 ms 182876 KB Output is correct
12 Correct 21 ms 182876 KB Output is correct
13 Correct 21 ms 182872 KB Output is correct
14 Correct 29 ms 182948 KB Output is correct
15 Correct 24 ms 182872 KB Output is correct
16 Correct 30 ms 182852 KB Output is correct
17 Correct 25 ms 183072 KB Output is correct
18 Correct 22 ms 182868 KB Output is correct