// Untill Addiction Stops.
# pragma GCC optimize("Ofast")
# include <bits/stdc++.h>
namespace ddr {
# define bpc(bt) __builtin_popcountll(bt)
# define bcl(bt) __builtin_clz(bt)
# define alr(v) rbegin(v), rend(v)
# define all(v) begin(v), end(v)
# define si(v) ((ll)v.size())
# define lob lower_bound
# define upb upper_bound
# define pub push_back
# define pob pop_back
# define mp make_pair
# define ins insert
# define se second
# define fi first
template <class T, size_t N> using ar = std::array <T, N>;
template <class T, class U> using pi = std::pair <T, U>;
template <class T> using pq = std::priority_queue <T>;
template <class T> using mt = std::multiset <T>;
template <class T> using ve = std::vector <T>;
template <class T> using qu = std::queue <T>;
typedef std::string str;
typedef long double ld;
typedef long long ll;
typedef bool bo;
typedef char ch;
using namespace std;
const ll inf = 1e18 + 18;
const ll sz = 3e5 + 15;
const ll md = 1e9 + 7;
const ll mo = 998244353;
}
using namespace ddr;
const ll sm = 4e2 + 8;
bo dp[sm][sm][sm];
ll pr[sm];
ll n, k;
bo cac(ll le, ll ri, ll co) {
if (dp[le][ri][co]) {
return dp[le][ri][co];
}
ll igo = pr[ri];
if (le) {
igo -= pr[le - 1];
}
ll oco = pr[n - 1] - igo - co;
if (co >= k) {
return 0;
} else if (oco >= k) {
return 1;
}
return !cac(le + 1, ri, oco) || !cac(le, ri - 1, oco);
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
str s;
cin >> n >> k >> s;
pr[0] = 'C' == s[0];
for (ll i = 1; i < n; i ++) {
pr[i] = pr[i - 1] + ('C' == s[i]);
}
cout << (cac(0, n - 1, 0) ? "DA" : "NE");
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
363 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
363 ms |
460 KB |
Output is correct |
13 |
Execution timed out |
1020 ms |
600 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |