#include <bits/stdc++.h>
using namespace std;
long long dp[100001][5][3][3];
long long n,m;
long long 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];
long long 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;
long long num = 1 ;
int ma =0 , mi = 0;
for(int i = 0;i<s.size();i++){
if(s[i]=='P'){
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);
num+=solve(i+1,ne,nma,nmi);
num%=m;
}
}
if(s[i]=='P')cnt++;
else cnt--;
ma = max(ma,cnt-2);
mi = max(mi,2-cnt);
}
cout<<num<<"\n";
}
Compilation message
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0;i<s.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
35428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
35412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
35496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
35508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
35412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
35460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
35412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35464 KB |
Output is correct |
2 |
Correct |
14 ms |
35540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35540 KB |
Output is correct |
2 |
Correct |
15 ms |
35540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35796 KB |
Output is correct |
2 |
Correct |
16 ms |
35996 KB |
Output is correct |
3 |
Correct |
16 ms |
35524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
37708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
37972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
42432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
43728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
114 ms |
65536 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
126 ms |
65536 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
146 ms |
65536 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
137 ms |
65536 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
148 ms |
65536 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |