Submission #1276685

#TimeUsernameProblemLanguageResultExecution timeMemory
1276685BuivietthanhLinear Garden (IOI08_linear_garden)C++20
100 / 100
58 ms36456 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long int n,m,dp[1000003][3][3]; char a[1000003]; int main() { srand(time(NULL)); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("inp.INP","r",stdin); //freopen("out.OUT","w",stdout); cin>>n>>m; for (int i=1;i<=n;i++) cin>>a[i]; dp[n+1][2][0]=1; for (int i=n;i>=1;i--) { for (int minn=-2;minn<=0;minn++) { for (int maxx=0;maxx<=2;maxx++) { ll min1=min(minn+1,0),max1=maxx+1; if (min1>=-2 && max1<=2) dp[i][min1+2][max1]+=dp[i+1][minn+2][maxx],dp[i][min1+2][max1]%=m; min1=minn-1,max1=max(maxx-1,0); if (min1>=-2 && max1<=2) dp[i][min1+2][max1]+=dp[i+1][minn+2][maxx],dp[i][min1+2][max1]%=m; } } } ll minn=0,maxx=0,sum=0; for (int i=1;i<=n;i++) { //cout<<i<<' '<<sum<<endl; ll p=(a[i]=='P'?1:-1); ll min1=min(minn+p,min(p,(ll)0)); ll max1=max(maxx+p,max(p,(ll)0)); if (min1<-2) { sum=0; break; } if (max1>2) { minn=min(minn-1,(ll)-1); maxx=max(maxx-1,(ll)0); if (minn<-2) { sum=0; break; } continue; } if (a[i]=='P' && minn-1>=-2) { minn--; maxx=max(maxx-1,(ll)0); for (int u=-2;u<=0;u++) { for (int v=0;v<=2;v++) { if (minn+u>=-2 && maxx+v<=2) { sum+=dp[i+1][u+2][v]; sum%=m; } } } } if (i==n) sum=(sum+1)%m; minn=min1; maxx=max1; } cout<<sum; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...