/*
-> Authored By : Ахмад <-
->IM COMING BACKK<-
*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define F first
#define S second
#define endl '\n'
#define pb emplace_back
#define sqrt sqrtl
#define clr(A, Val) memset(A, Val, sizeof(A));
#define what_is(x) cerr << "->" << (#x) << " = " << x << endl
const int mod = 1e9 + 7, mod2 = 1e9 + 9, OO = 0x3f3f3f3f;
const long long lOO = 0x3f3f3f3f3f3f3f3f;
int add(ll a, ll b) { return (a + b) % mod; }
int mul(ll a, ll b) { return 1LL * a * b % mod; }
long long intlog(ll base, ll x) { return (log(x) / log(base)); }
long long Ceil(ll a, ll b) { return (a + b - 1) / b; }
template <typename T>
int32_t size_i(T &container) {
return static_cast<int32_t>(container.size());
}
// MIST!?!?!?!?!?
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
//-> U Sure?!
template <typename T1, typename T2>
using safe_map = unordered_map<T1, T2, custom_hash>;
template <typename T>
istream &operator>>(istream &istream, vector<T> &v) {
for (auto &it : v) cin >> it;
return istream;
}
template <typename T>
ostream &operator<<(ostream &ostream, vector<T> &C) {
for (auto &it : C) cout << it << " ";
return ostream;
}
// Think again?!
void ________________________________() {
int ____ = 0;
#ifndef ONLINE_JUDGE
____ = 1;
#endif
if (____ == 0) {
cin.tie(0)->sync_with_stdio(0);
}
}
ll power(ll b, ll p) {
if (p == 0) return 1;
ll temp = power(b, p / 2);
temp = temp * temp;
if (p & 1) temp = temp * b;
return temp;
}
// OK?!
const int N = 3e5 + 1, BASE = 26, BASE2 = 37;
ll n, k;
string s;
ll pre[N]{}, dp[358][358][358];
ll get(ll st, ll ed) {
if (st > ed) swap(st, ed);
if (st < 0) return 0;
if (ed >= n) return 0;
if (st == 0) return pre[ed];
return pre[ed] - pre[st - 1];
}
ll solve(ll l, ll r, ll a) {
if (l > r) return 0;
ll ans1 = get(0, l - 1) + get(r + 1, n - 1) - a;
ans1 = max(ans1, 0ll);
// cout << ans1 << " " << l << r << a << endl;
if (ans1 > k) return 1;
if (a > k) {
return 0;
}
if (dp[l][r][a] != -1) return dp[l][r][a];
ll op1 = 0, op2 = 0, op3 = 0, op4 = 0; // we have 4 options
op1 = solve(l + 2, r, a + (s[l] == 'C'));
op2 = solve(l + 1, r - 1, a + (s[l] == 'C'));
op3 = solve(l, r - 2, a + (s[r] == 'C'));
op4 = solve(l + 1, r - 1, a + (s[r] == 'C'));
return dp[l][r][a] = max({op1, op2, op3, op4});
}
void TestCases() {
clr(dp, -1);
cin >> n >> k >> s;
pre[0] = (s[0] == 'C');
for (ll i = 1; i < n; ++i) {
pre[i] = pre[i - 1] + (s[i] == 'C');
}
// cout << get(n - 1, n - 1) << endl;
ll o = (s[0] == 'C') + (s[n - 1] == 'C');
bool V = solve(0, n - 1, o);
if (V == 0)
cout << "DA" << endl;
else
cout << "NE" << endl;
}
int main() {
________________________________();
ll ____________ = 1;
// cin >> ____________;
cout << fixed << setprecision(12);
while ((____________)--) {
TestCases();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
359560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
359560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
359560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
