Submission #525889

#TimeUsernameProblemLanguageResultExecution timeMemory
525889BackNoobKamenčići (COCI21_kamencici)C++14
70 / 70
45 ms44528 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define endl '\n' #define MASK(i) (1LL << (i)) #define ull unsigned long long #define ld long double #define pb push_back #define all(x) (x).begin() , (x).end() #define BIT(x , i) ((x >> (i)) & 1) #define TASK "task" #define sz(s) (int) (s).size() using namespace std; const int mxN = 357; const int inf = 1e9 + 277; const int mod = 1e9 + 7; const ll infll = 1e18 + 7; const int base = 307; const int LOG = 20; template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } int n , k; string s; bool dp[mxN][mxN][mxN]; bool vis[mxN][mxN][mxN]; int pre[mxN]; int suf[mxN]; bool sol(int l , int r , int have) { if(l > r) { if(have >= k) return false; return true; } int x = pre[l - 1] + suf[r + 1] - have; if(have >= k) return false; if(x >= k) return true; bool &res = dp[l][r][have]; if(vis[l][r][have] == true) return res; vis[l][r][have] = true; res |= !sol(l + 1 , r , x); res |= !sol(l , r - 1 , x); return res; } void solve() { cin >> n >> k; cin >> s; for(int i = 1 ; i <= n ; i++) pre[i] = pre[i - 1] + (s[i - 1] == 'C'); for(int i = n ; i >= 1 ; i--) suf[i] = suf[i + 1] + (s[i - 1] == 'C'); if(sol(1 , n , 0) == true) cout << "DA"; else cout << "NE"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen(TASK".in" , "r" , stdin); //freopen(TASK".out" , "w" , stdout); int tc = 1; //cin >> tc; while(tc--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...