#include<iostream>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
const int MAXN=360, INF=1000000000;
int arr[MAXN], n, k, dp[MAXN][MAXN][MAXN];
string str;
int main(){
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k >> str;
dforn(i, n) for(int j=i+2 + (n&1); j<=n; j+=2) forn(can, k){
int v1=0, v2=0;
if(can>=(str[i]=='C')){
int dif = can-(str[i]=='C');
v1=min(dp[i+1][j-1][dif] + (str[j-1]=='C'), dp[i+2][j][dif] + (str[i+1]=='C'));
}
if(can>=(str[j-1]=='C')){
int dif = can-(str[j-1]=='C');
v2=min(dp[i+1][j-1][dif] + (str[i]=='C'), dp[i][j-2][dif] + (str[j-2]=='C'));
}
dp[i][j][can]=max(v1, v2);
}
int mx=0;
forn(i, k) mx=max(mx, dp[0][n][i]);
cout << (mx>=k? "DA\n" : "NE\n");
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
528 KB |
Output is correct |
7 |
Correct |
2 ms |
2124 KB |
Output is correct |
8 |
Correct |
1 ms |
1748 KB |
Output is correct |
9 |
Correct |
1 ms |
2132 KB |
Output is correct |
10 |
Correct |
2 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1876 KB |
Output is correct |
12 |
Correct |
2 ms |
1876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
528 KB |
Output is correct |
7 |
Correct |
2 ms |
2124 KB |
Output is correct |
8 |
Correct |
1 ms |
1748 KB |
Output is correct |
9 |
Correct |
1 ms |
2132 KB |
Output is correct |
10 |
Correct |
2 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1876 KB |
Output is correct |
12 |
Correct |
2 ms |
1876 KB |
Output is correct |
13 |
Correct |
46 ms |
87256 KB |
Output is correct |
14 |
Correct |
43 ms |
86244 KB |
Output is correct |
15 |
Correct |
35 ms |
78412 KB |
Output is correct |
16 |
Correct |
50 ms |
85324 KB |
Output is correct |
17 |
Correct |
74 ms |
86448 KB |
Output is correct |
18 |
Correct |
47 ms |
85328 KB |
Output is correct |