#include<bits/stdc++.h>
using namespace std;
const int N = 350, inf = 1e9;
int n, k;
string s;
vector<vector<vector<int> > > dp(N, vector<vector<int> > (N, vector<int> (N)));
int main()
{
cin >> n >> k;
cin >> s;
for(int l = k - 1; l >= 0; l--)
for(int i = n - 1; i >= 0; i--)
{
if(s[i] == 'P') dp[i][i][l] = 0;
else if((n - 1) & 1) dp[i][i][l] = 1;
else dp[i][i][l] = -inf;
// cerr << "dp[" << i << "][" << i << "][" << l << "] = " << dp[i][i][l] << endl;
for(int j = i + 1; j < n; j ++)
{
if((n - (j - i + 1)) % 2 == 0) // if this is player 1 turn
{
// cerr << i << ' ' << j << "I\n";
dp[i][j][l] = -inf;
if(s[i] == 'C' && l + 1 < k)
dp[i][j][l] = max(dp[i][j][l], dp[i + 1][j][l + 1]);
else if(s[j] == 'P')
dp[i][j][l] = max(dp[i][j][l], dp[i + 1][j][l]);
if(s[j] == 'C' && l + 1 < k)
dp[i][j][l] = max(dp[i][j][l], dp[i][j-1][l+1]);
else if(s[j] == 'P')
dp[i][j][l] = max(dp[i][j][l], dp[i][j-1][l]);
}
else
{
dp[i][j][l] = inf;
if(s[i] == 'C')
dp[i][j][l] = min(dp[i][j][l], dp[i + 1][j][l] + 1);
else
dp[i][j][l] = min(dp[i][j][l], dp[i + 1][j][l]);
if(s[j] == 'C')
dp[i][j][l] = min(dp[i][j][l], dp[i][j-1][l] + 1);
else
dp[i][j][l] = min(dp[i][j][l], dp[i][j-1][l]);
}
// cerr << "dp[" << i << "][" << j << "][" << l << "] = " << dp[i][j][l] << endl;
}
}
// cerr << dp[0][n-1][0] << endl;
bool ans = (dp[0][n - 1][0] >= k);
cout << (ans ? "DA" : "NE") << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
172452 KB |
Output is correct |
| 2 |
Incorrect |
129 ms |
172372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
172452 KB |
Output is correct |
| 2 |
Incorrect |
129 ms |
172372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
172452 KB |
Output is correct |
| 2 |
Incorrect |
129 ms |
172372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
