#include <bits/stdc++.h>
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
using namespace std;
typedef long long ll;
const int CS[] = { 2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 1, 1, 1 };
const int CE[] = { 2, 3, 3, 4, 4, 4, 2, 2, 2, 2, 2, 3, 3, 3 };
const int CX[] = { 2, 2, 3, 2, 3, 4, 1, 2, 0, 1, 2, 1, 2, 3 };
const int MAXN = 1000002;
int dp[MAXN][14];
int A[MAXN];
int N, MOD, Ans;
int main() {
scanf("%d%d", &N, &MOD);
for(int i = 1; i <= N; i++) {
char c; scanf(" %c", &c);
A[i] = (c == 'P' ? 1 : -1);
}
for(int i = 0; i < 14; i++) dp[N][i] = 1;
for(int i = N; i--;) {
for(int j = 0; j < 14; j++) {
int &ret = dp[i][j];
int s = CS[j], e = CE[j], x = CX[j];
for(int nx : {x-1, x+1}) {
int ns = min(s, nx), ne = max(e, nx);
if(ne-ns > 2) continue;
int nj = 0; for(; CS[nj] != ns || CE[nj] != ne || CX[nj] != nx; nj++);
ret = (ret + dp[i+1][nj]) % MOD;
}
}
}
for(int i = 1, s = 2, e = 2, x = 2; i <= N; i++) {
if(A[i] < 0) {
x--;
upmin(s, x);
upmax(e, x);
continue;
}
{
int xx = x-1, ss = min(s, xx), ee = max(e, xx);
if(ee-ss < 3) {
int j = 0; for(; j < 14 && (ss != CS[j] || ee != CE[j] || xx != CX[j]); j++);
if(j < 14) Ans = (Ans + dp[i][j]) % MOD;
}
}
x++;
upmin(s, x);
upmax(e, x);
}
cout << (Ans+1) % MOD << endl;
return 0;
}
Compilation message
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &MOD);
~~~~~^~~~~~~~~~~~~~~~~~
linear_garden.cpp:20:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char c; scanf(" %c", &c);
~~~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
632 KB |
Output is correct |
3 |
Correct |
4 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
1540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
1656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
4028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
4736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
18904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
176 ms |
24412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
222 ms |
31076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
270 ms |
37524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
433 ms |
59972 KB |
Output is correct |
2 |
Correct |
431 ms |
60040 KB |
Output is correct |
3 |
Correct |
431 ms |
60024 KB |
Output is correct |