#include <bits/stdc++.h>
using namespace std;
map<array<array<int, 2>, 2>, int> dp; //1 ha az elso nyer, 0 ha elso veszt, -1 ha ismeretlen
int n, k;
string a;
bool h(int i, int j, array<int, 2> p, int s){ //intervallum i, j, p[0]je van az elsonek, p[1] van a masodiknak, sedik jatekos van
array<int, 2> x = {i, j};
array<array<int, 2>, 2> ind = {x, p};
if(dp.count(ind) != 0) return dp[ind];
if(p[0] >= k) return dp[ind] = 0; //elso veszt
if(p[1] >= k) return dp[ind] = 1; //elso nyer
array<int, 2> p2 = p;
if(a[i] == 'C') p2[s]++;
bool o1 = h(i + 1, j, p2, 1 - s);
p2 = p;
if(a[j] == 'C') p2[s]++;
bool o2 = h(i, j - 1, p2, 1 - s);
if(s == 0){
if(o1 || o2) return dp[ind] = 1; //ha van nyer
else return dp[ind] = 0;
}
if(!o1 || !o2) return dp[ind] = 0; //ha van veszto
return dp[ind] = 1; //ha mindketto nyero az elsonek
}
int main() {
cin >> n >> k;
cin >> a;
if(h(0, n - 1, {0, 0}, 0)) cout << "DA";
else cout << "NE";
}
Compilation message
Main.cpp: In function 'bool h(int, int, std::array<int, 2>, int)':
Main.cpp:12:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
12 | if(p[0] >= k) return dp[ind] = 0; //elso veszt
Main.cpp:13:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
13 | if(p[1] >= k) return dp[ind] = 1; //elso nyer
Main.cpp:23:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
23 | if(o1 || o2) return dp[ind] = 1; //ha van nyer
Main.cpp:24:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
24 | else return dp[ind] = 0;
Main.cpp:26:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
26 | if(!o1 || !o2) return dp[ind] = 0; //ha van veszto
Main.cpp:27:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
27 | return dp[ind] = 1; //ha mindketto nyero az elsonek
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
2 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
2 ms |
336 KB |
Output is correct |
| 12 |
Correct |
2 ms |
600 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
2 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
2 ms |
336 KB |
Output is correct |
| 12 |
Correct |
2 ms |
600 KB |
Output is correct |
| 13 |
Correct |
1 ms |
504 KB |
Output is correct |
| 14 |
Correct |
953 ms |
68544 KB |
Output is correct |
| 15 |
Correct |
118 ms |
11336 KB |
Output is correct |
| 16 |
Correct |
756 ms |
54344 KB |
Output is correct |
| 17 |
Correct |
244 ms |
22604 KB |
Output is correct |
| 18 |
Correct |
76 ms |
8004 KB |
Output is correct |
