Submission #1249144

#TimeUsernameProblemLanguageResultExecution timeMemory
1249144al95ireyizKamenčići (COCI21_kamencici)C++20
70 / 70
178 ms350628 KiB
//*** Bismillah ***// #pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector") #include <bits/stdc++.h> using namespace std; #if !defined(ONLINE_JUDGE) and !defined(EVAL) #include "template/debug.h" #else #define d(x...) #endif #define fr first #define er erase #define sc second #define in insert #define ll long long #define pb push_back #define vll vector<ll> #define pll pair<ll,ll> #define ull unsigned ll #define vpll vector<pll> #define len(x) (ll) x.size() #define all(x) x.begin(),x.end() const ll INF = 1e9; const ll INFL = 1e18; const ll MOD = 1e9+7; // const ll MOD = 998244353; const ll maxn = 2e5+5; ll n,m,k=0; string s; // i -> sol serhed // j -> sag serhed // q -> A-nin goturduyu qirmizi das sayi ll dp[355][355][355], v[maxn]; ll f(ll l = 1, ll r = n, ll nw = 0, ll a = 0, ll b = 0){ if(dp[l][r][a] != -1) return dp[l][r][a]; if(a >= m or b >= m) return dp[l][r][a] = 1; if(nw == 0) return dp[l][r][a] = (!f(l + 1, r, !nw, a + v[l], b) or !f(l, r - 1, !nw, a + v[r], b)); else return dp[l][r][a] = (!f(l + 1, r, !nw, a, b + v[l]) or !f(l, r - 1, !nw, a, b + v[r])); } void _(ll &tt){ cin >> n >> m; cin >> s; s = ' ' + s; memset(dp, -1, sizeof(dp)); for(ll i = 1; i <= n; i ++) v[i] = (s[i] == 'C'); cout << (f() ? "DA\n" : "NE\n"); } signed main() { ll tm = clock(); cin.tie(0)->sync_with_stdio(0); ll t = 1; // cin >> t; for(ll tt = 1; tt <= t; tt ++) { _(tt); } cerr << "\n\033[1;31mTime: \033[1;30m" \ << (double)(clock()-tm)/1000000 << "\033[1;32m seconds\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...