#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |