#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int d[3][3][6][1000001];
char s[1000001];
int n, m;
int f(int mxL, int mxP, int bal, int k) {
int v = bal - 2;
if ((mxP - v > 2) || (mxL + v > 2)) return 0;
if (k == 0) return 1;
int& ret = d[mxL][mxP][bal][k];
if (ret >= 0) return ret;
ret = 0;
ret += f(max(mxL, -v + 1), mxP, v + 1, k - 1);
ret += f(mxL, max(mxP, v + 1), v + 3, k - 1);
ret %= m;
return ret;
}
int main() {
memset(d, -1, sizeof(d));
scanf("%d %d %s", &n, &m, s);
int res = 1;
int curmxL = 0, curmxP = 0, cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'P') {
res += f(max(curmxL, -cnt + 1), curmxP, cnt + 1, n - 1 - i);
if (res >= m) res -= m;
}
if (s[i] == 'L') cnt--;
else cnt++;
curmxL = max(curmxL, -cnt);
curmxP = max(curmxP, cnt);
}
printf("%d\n", res);
return 0;
}
Compilation message
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %s", &n, &m, s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
182 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
198 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
184 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
183 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
185 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
190 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
191 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
193 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
195 ms |
196608 KB |
Output is correct |
2 |
Correct |
180 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
196608 KB |
Output is correct |
2 |
Correct |
183 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
199 ms |
196608 KB |
Output is correct |
2 |
Correct |
189 ms |
196608 KB |
Output is correct |
3 |
Correct |
179 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
190 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
211 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
214 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
283 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
267 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
343 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
406 ms |
196608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
550 ms |
196608 KB |
Output is correct |
2 |
Correct |
345 ms |
196608 KB |
Output is correct |
3 |
Correct |
535 ms |
196608 KB |
Output is correct |