#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N, K;
vector<int> v;
array<int, 2> memo[400][400];
bool vis[400][400];
array<int, 2> solve(int a, int b, bool turn) {
if (a > b) return array<int, 2>{0, 0};
if (vis[a][b]) return memo[a][b];
vis[a][b] = 1;
auto x = solve(a + 1, b, !turn);
x[turn] += v[a];
auto y = solve(a, b - 1, !turn);
y[turn] += v[b];
if (y[0] < x[0]) swap(x, y);
if (turn) swap(x, y);
if (x[turn] >= K) {
x[turn] = 1e9;
x[!turn] = -1e9;
}
// if (x[1] >= K && x[0] < 1e8) x[1] = 1e9;
// if (x[0] >= K && x[1] < 1e8) x[0] = 1e9;
return memo[a][b] = x;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> K;
string x;
cin >> x;
for (char i : x) {
v.pb(i == 'C');
}
assert(v.size() == N);
if (solve(0, N - 1, 0)[0] < 1e8)
cout << "DA\n";
else
cout << "NE\n";
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Main.cpp:2:
Main.cpp: In function 'int main()':
Main.cpp:44:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
44 | assert(v.size() == N);
| ~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
