#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()
const int MAXN = 355, INF = 2e9+50;
const ull INF_L = (ull)1e19+500;
int n,k;
string A;
bool dp[MAXN][MAXN][MAXN];
bool dp2[MAXN][MAXN][MAXN];
void solve()
{
cin >> n >> k >> A;
rep(i,n)
{
if(A[i] == 'P')
{
dp2[i][i][1] = 1;
}
}
for(int len = 2; len <= n; ++len)
{
for(int j = 0; j+len-1 < n; ++j)
{
int l = j, p = j+len-1;
for(int c = 1; c <= k; ++c)
{
dp[l][p][c] = 0;
if(c == 1)
{
if(A[l] == 'P' and !dp[l+1][p][c]) dp[l][p][c] = 1;
if(A[p] == 'P' and !dp[l][p-1][c]) dp[l][p][c] = 1;
}
else
{
if(A[l] == 'C' and !dp2[l+1][p][c]) dp[l][p][c] = 1;
if(A[l] == 'P' and !dp[l+1][p][c]) dp[l][p][c] = 1;
if(A[p] == 'C' and !dp2[l][p-1][c-1]) dp[l][p][c] = 1;
if(A[p] == 'P' and !dp[l][p-1][c]) dp[l][p][c] = 1;
if(A[l] == 'C' and !dp[l+1][p][c-1]) dp2[l][p][c] = 1;
if(A[l] == 'P' and !dp2[l+1][p][c]) dp2[l][p][c] = 1;
if(A[p] == 'C' and !dp[l][p-1][c-1]) dp2[l][p][c] = 1;
if(A[p] == 'P' and !dp2[l][p-1][c]) dp2[l][p][c] = 1;
}
//cout << "L: " << l << " P: " << p << " C: " << c << " VAL: " << dp[l][p][c] << endl;
}
}
}
if(dp[0][n-1][k] == 1) cout << "DA" << '\n';
else cout << "NE" << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
