#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
const int INF = 1e9;
int n, m;
char str[N];
int dp[N][15];
inline int add(int a, int b) { return (a+b)%m; }
inline int pos(int mn, int mx, int bal)
{
if (mn == 0) {
if (mx == 0) return 0;
if (mx == 1) return 1+bal;
if (mx == 2) return 3+bal;
} else if (mn == -1) {
if (mx == 0) return 7+bal;
if (mx == 1) return 9+bal;
} else if (mn == -2) {
if (mx == 0) return 13+bal;
}
return 14;
}
int main()
{
scanf("%d%d %s", &n, &m, str);
for (int i = n; i >= 0; --i) {
for (int mn = -2; mn <= 0; ++mn) {
for (int mx = max(mn, 0); mx-mn <= 2; ++mx) {
for (int bal = mn; bal <= mx; ++bal) {
int j = pos(mn, mx, bal);
if (i == n) dp[i][j] = 1;
else dp[i][j] = add(dp[i+1][pos(min(mn, bal-1), mx, bal-1)], dp[i+1][pos(mn, max(mx, bal+1), bal+1)]);
}
}
}
}
int mn = 0, mx = 0, bal = 0, ans = 1;
for (int i = 0; i < n; ++i) {
if (str[i] == 'P') {
ans = add(ans, dp[i+1][pos(min(mn, bal-1), mx, bal-1)]);
++bal;
mx = max(mx, bal);
} else {
--bal;
mn = min(mn, bal);
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d %s", &n, &m, str);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
620 KB |
Output is correct |
2 |
Correct |
3 ms |
620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
656 KB |
Output is correct |
2 |
Correct |
2 ms |
656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
836 KB |
Output is correct |
2 |
Correct |
4 ms |
964 KB |
Output is correct |
3 |
Correct |
4 ms |
964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
1904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
2160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
4336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
5104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
19236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
100 ms |
24720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
168 ms |
31344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
140 ms |
37952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
196 ms |
60356 KB |
Output is correct |
2 |
Correct |
287 ms |
61336 KB |
Output is correct |
3 |
Correct |
292 ms |
62464 KB |
Output is correct |