Submission #862192

#TimeUsernameProblemLanguageResultExecution timeMemory
8621923omar_ahmedKamenčići (COCI21_kamencici)C++17
70 / 70
98 ms344776 KiB
#include <bits/stdc++.h> using namespace std ; #define int long long #define endl '\n' #define all(a) a.begin() , a.end() #define alr(a) a.rbegin() , a.rend() int n, k; string x; vector < int > pre, suf; int dp[353][353][353]; int solve(int l, int r, int red) { int type = ((l - 1) + (n - r)) % 2; if(red == k) { return 0; } int opp = pre[l - 1] + suf[r + 1] - red; if(opp == k) { return 1; } if(dp[l][r][red] != -1) return dp[l][r][red]; dp[l][r][red] = 0; if(type == 0) { if(solve(l + 1, r, red + (x[l] == 'C'))) return dp[l][r][red] = 1; if(solve(l, r - 1, red + (x[r] == 'C'))) return dp[l][r][red] = 1; return 0; } else { if(!solve(l + 1, r, red)) return 0; if(!solve(l, r - 1, red)) return 0; return dp[l][r][red] = 1; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n >> k >> x; pre = suf = vector < int > (n + 2); x = "%" + x; for(int i = 1 ; i <= n ; i++) { pre[i] = pre[i - 1] + (x[i] == 'C'); } for(int i = n ; i >= 1 ; i--) { suf[i] = suf[i + 1] + (x[i] == 'C'); } memset(dp, -1, sizeof(dp)); if(solve(1, n, 0)) { cout << "DA" << endl; } else { cout << "NE" << endl; } return 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...