#include <bits/stdc++.h>
using namespace std;
int dp[500001][5][3][3];
int n,m;
int solve(int i,int cnt,int ma,int mi){
if(i==n){
return 1;
}
if(dp[i][cnt][ma][mi]!=-1)return dp[i][cnt][ma][mi];
int c1 = 0;
{
int ne = cnt+1;
int r = 2+ma;
int l = 2-mi;
if(abs(ne-r)<=2&&abs(ne-l)<=2){
int nma = max(ma,ne-2);
int nmi = max(mi,2-ne);
c1+=solve(i+1,ne,nma,nmi);
c1%=m;
}
}
{
int ne = cnt-1;
int r = 2+ma;
int l = 2-mi;
if(abs(ne-r)<=2&&abs(ne-l)<=2){
int nma = max(ma,ne-2);
int nmi = max(mi,2-ne);
c1+=solve(i+1,ne,nma,nmi);
c1%=m;
}
}
return dp[i][cnt][ma][mi] = c1;
}
int main(){
cin>>n>>m;
string s;cin>>s;
memset(dp,-1,sizeof dp);
int cnt = 2;
int num = 1;
int ma =0,mi = 0;
int mm[n],nn[n],cc[n];
for(int i = 0;i<s.size();i++){
cc[i] = cnt;
mm[i] = ma;
nn[i] = mi;
if(s[i]=='P')cnt++;
else cnt--;
ma = max(ma,cnt-2);
mi = max(mi,2-cnt);
}
int dp[2][5][3][3];
for(int i = 0;i<5;i++){
for(int j = 0;j<3;j++){
for(int k = 0;k<3;k++)dp[n%2][i][j][k] = 1;
}
}
for(int i = n-1;i>=0;i--){
if(s[i]=='P'){
int ne = cc[i]-1;
int r = 2+mm[i];
int l = 2-nn[i];
if(abs(ne-r)<=2&&abs(ne-l)<=2){
int nma = max(mm[i],ne-2);
int nmi = max(nn[i],2-ne);
num+=dp[!(i%2)][ne][nma][nmi];
num%=m;
}
}
for(int j = 0;j<5;j++){
for(int k = 0;k<3;k++){
for(int e = 0;e<3;e++){
int c1 = 0;
{
int ne = j+1;
int r = 2+k;
int l = 2-e;
if(abs(ne-r)<=2&&abs(ne-l)<=2){
int nma = max(k,ne-2);
int nmi = max(e,2-ne);
c1+=dp[!(i%2)][ne][nma][nmi];
c1%=m;
}
}
{
int ne = j-1;
int r = 2+k;
int l = 2-e;
if(abs(ne-r)<=2&&abs(ne-l)<=2){
int nma = max(k,ne-2);
int nmi = max(e,2-ne);
c1+=dp[!(i%2)][ne][nma][nmi];
c1%=m;
}
}
dp[i%2][j][k][e] = c1;
}
}
}
}
cout<<num<<"\n";
}
Compilation message
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0;i<s.size();i++){
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
31 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
33 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
34 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
31 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
29 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
29 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
31 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
35 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
36 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
40 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
43 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
54 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |