Submission #1187297

#TimeUsernameProblemLanguageResultExecution timeMemory
1187297MirbalaKamenčići (COCI21_kamencici)C++20
70 / 70
36 ms44360 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define mir signed #define pii pair<int, int> #define tup tuple<int, int, int> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define bs << ' ' #define bss << ' ' << #define endl \ << '\n' #define each(i, x) for (auto &i : x) #define say(x) cout << x endl; #define fastt \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); #define itn int const int inf = 1e9; const long long inff = 2e18; const int mod = 1e18; vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0}; void maxx(int &a, int b) { a = max(a, b); } void minn(int &a, int b) { a = min(a, b); } int gcd(int a, int b) { if (!b) return a; return gcd(b, a % b); } int lcm(int a, int b) { return a / gcd(a, b) * b; } int cel(int a, int b) { return (a - 1) / b + 1; } int binpow(int a, int b) { if (!b) return 1; int res = binpow(a % mod, b / 2); res = (res * res) % mod; if (b & 1) res = (res * (a % mod)) % mod; return res; } const int sq = 100000; string xorr(string a, string b) { if (a.size() < b.size()) swap(a, b); int j = b.size() - 1; for (int i = a.size() - 1; i >= 0; --i) { if (j < 0) break; a[i] = char((a[i] - '0') ^ (b[j] - '0') + '0'); j--; } return a; } // int vur(int a, int b){ // return (((a * b) % mod) + mod) % mod; // } struct Node { int l, r; unsigned long long lazy, sum; Node *L = nullptr, *R = nullptr; Node(int ll, int rr) { l = ll; r = rr; lazy = sum = 0; } void ext() { if (lazy && l != r) { int mid = (l + r) / 2; if (!L) L = new Node(l, mid); if (!R) R = new Node(mid + 1, r); L->lazy += lazy; R->lazy += lazy; L->sum += lazy * (mid - l + 1); R->sum += lazy * (r - mid); } lazy = 0; } void add(int lf, int rf, int k) { if (l >= lf && rf >= r) { lazy += k; sum += (r - l + 1) * k; return; } if (l > rf || r < lf) return; ext(); int mid = (l + r) >> 1; if (!L && !(mid < lf || l > rf)) L = new Node(l, mid); if (!R && !(r < lf || mid + 1 > rf)) R = new Node(mid + 1, r); if (!(mid < lf || l > rf)) L->add(lf, rf, k); if (!(r < lf || mid + 1 > rf)) R->add(lf, rf, k); sum = (L ? L->sum : 0) + (R ? R->sum : 0); } unsigned long long query(int lf, int rf) { if (lf > r || rf < l) return 0; if (l >= lf && rf >= r) return sum; int mid = (l + r) >> 1; ext(); return (L && !(mid < lf || l > rf) ? L->query(lf, rf) : 0) + (R && !(r < lf || mid + 1 > rf) ? R->query(lf, rf) : 0); } }; // const int sz = 355; bool dp[355][355][355]; bool vis[355][355][355]; string s; int k; bool dfs(int l,int r,int biz,int req){ if(biz >= k)return 0; if(req >= k)return 1; if(vis[l][r][biz])return dp[l][r][biz]; vis[l][r][biz] = 1; bool sol = dfs(l+1,r,req,biz + (s[l] == 'C')),sag = dfs(l,r-1,req,biz + (s[r] == 'C')); sol ^= 1; sag ^= 1; return dp[l][r][biz] = (sol | sag); } void solve() { int n; cin >> n >> k; cin >> s; s = '.' + s; if(dfs(1,n,0,0))say("DA") else say("NE") } mir main() { fastt int t = 1; // cin >> t; for (int tt = 1; tt <= t; ++tt) { // cout << "Case " << tt << ": "; solve(); } // int n; // while(cin >> n){ // solve(n); // } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...