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