#include <bits/stdc++.h>
#define SQR(x) (1LL * ((x) * (x)))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(s) (int)s.size()
#define prev __prev
#define next __next
#define left __left
#define right __right
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int ui;
using namespace std;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll INFLL = (ll)2e18 + 7LL;
const ld PI = acos(-1);
const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
template<class BUI, class TRONG>
bool minimize(BUI &x, const TRONG y){
if(x > y){
x = y;
return true;
} else return false;
}
template<class BUI, class TRONG>
bool maximize(BUI &x, const TRONG y){
if(x < y){
x = y;
return true;
} else return false;
}
/* Author : Bui Nguyen Duc Trong, Luong Van Chanh High School for the gifted*/
/* Template is copied by Trong */
/** Losing in Provincial Contests **/
/** TRYING HARDER**/
/** ORZ **/
/* -----------------[ MAIN CODE GOES HERE ]----------------- */
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 355;
int n, k;
string s;
int c[N];
int f[N][N][N];
int F(int l, int r, int picked){
if(f[l][r][picked] != -1) return f[l][r][picked];
int ans = 0;
int L = picked + (s[l] == 'C'), R = picked + (s[r] == 'C');
int e = c[l - 1] + c[n] - c[r] - picked;
if(L < k) maximize(ans, 1 ^ F(l + 1, r, e));
if(R < k) maximize(ans, 1 ^ F(l, r - 1, e));
return f[l][r][picked] = ans;
}
void solve(){
cin >> n >> k;
cin >> s;
s = ' ' + s;
for(int i = 1; i <= n; i++) c[i] = c[i - 1] + (s[i] == 'C');
memset(f, -1, sizeof f);
cout << (F(1, n, 0) ? "DA" : "NE") << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
const bool multitest = 0;
int tt = 1; if(multitest) cin >> tt;
while( tt-- ){
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
175444 KB |
Output is correct |
2 |
Correct |
22 ms |
175336 KB |
Output is correct |
3 |
Correct |
22 ms |
175452 KB |
Output is correct |
4 |
Correct |
20 ms |
175452 KB |
Output is correct |
5 |
Correct |
21 ms |
175452 KB |
Output is correct |
6 |
Correct |
21 ms |
175452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
175444 KB |
Output is correct |
2 |
Correct |
22 ms |
175336 KB |
Output is correct |
3 |
Correct |
22 ms |
175452 KB |
Output is correct |
4 |
Correct |
20 ms |
175452 KB |
Output is correct |
5 |
Correct |
21 ms |
175452 KB |
Output is correct |
6 |
Correct |
21 ms |
175452 KB |
Output is correct |
7 |
Correct |
21 ms |
175704 KB |
Output is correct |
8 |
Correct |
21 ms |
175452 KB |
Output is correct |
9 |
Correct |
22 ms |
175448 KB |
Output is correct |
10 |
Correct |
21 ms |
175440 KB |
Output is correct |
11 |
Correct |
21 ms |
175448 KB |
Output is correct |
12 |
Correct |
22 ms |
175440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
175444 KB |
Output is correct |
2 |
Correct |
22 ms |
175336 KB |
Output is correct |
3 |
Correct |
22 ms |
175452 KB |
Output is correct |
4 |
Correct |
20 ms |
175452 KB |
Output is correct |
5 |
Correct |
21 ms |
175452 KB |
Output is correct |
6 |
Correct |
21 ms |
175452 KB |
Output is correct |
7 |
Correct |
21 ms |
175704 KB |
Output is correct |
8 |
Correct |
21 ms |
175452 KB |
Output is correct |
9 |
Correct |
22 ms |
175448 KB |
Output is correct |
10 |
Correct |
21 ms |
175440 KB |
Output is correct |
11 |
Correct |
21 ms |
175448 KB |
Output is correct |
12 |
Correct |
22 ms |
175440 KB |
Output is correct |
13 |
Correct |
21 ms |
175452 KB |
Output is correct |
14 |
Correct |
35 ms |
175452 KB |
Output is correct |
15 |
Correct |
24 ms |
175452 KB |
Output is correct |
16 |
Correct |
33 ms |
175452 KB |
Output is correct |
17 |
Correct |
28 ms |
175452 KB |
Output is correct |
18 |
Correct |
24 ms |
175476 KB |
Output is correct |