Submission #1266257

#TimeUsernameProblemLanguageResultExecution timeMemory
1266257canhnam357Kamenčići (COCI21_kamencici)C++20
70 / 70
89 ms168776 KiB
#include <bits/stdc++.h> using namespace std; #define N 350 int dp[N][N][N], g[N][N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); memset(dp, -1, sizeof dp); int n, k; cin >> n >> k; string s; cin >> s; int sum = 0; for (int i = 0; i < n; i++) { int f = 0; for (int j = n - 1; j >= i; j--) { g[i][j] = f + sum; f += (s[j] == 'C'); } sum += (s[i] == 'C'); } function<int(int, int, int)> solve = [&](int fi, int l, int r) { if (l > r) return 1; // cout << fi << ' ' << l << ' ' << r << '\n'; // if (fi < 0 || fi > k) exit(0); if (dp[fi][l][r] != -1) return dp[fi][l][r]; int ans = 1; if (fi > 1) { if (s[l] == 'C') ans &= solve(2 * k - g[l][r] - fi, l + 1, r); else ans &= solve(2 * k - g[l][r] - fi, l + 1, r); if (s[r] == 'C') ans &= solve(2 * k - g[l][r] - fi, l, r - 1); else ans &= solve(2 * k - g[l][r] - fi, l, r - 1); } else { if (s[l] == 'C' && s[r] == 'C') return dp[fi][l][r] = 0; if (s[l] == 'P') ans &= solve(2 * k - g[l][r] - fi, l + 1, r); if (s[r] == 'P') ans &= solve(2 * k - g[l][r] - fi, l, r - 1); } return dp[fi][l][r] = 1 - ans; }; cout << (solve(k, 0, n - 1) ? "DA" : "NE") << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...