Submission #228373

#TimeUsernameProblemLanguageResultExecution timeMemory
228373FieryPhoenixLinear Garden (IOI08_linear_garden)C++11
90 / 100
216 ms65536 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; #define INF 2001001001 #define MOD 1000000007 int N,M; string S; int dp[1000001][3][3][2];//index, max(L-P), max(P-L), 0 for L int main() { //ios_base::sync_with_stdio(0);cin.tie(0); //freopen (".in","r",stdin); //freopen (".out","w",stdout); cin>>N>>M; cin>>S; dp[N][0][0][0]=1; for (int i=N-1;i>=0;i--){ //adding L for (int j=0;j<2;j++) for (int k=0;k<=2;k++) for (int l=0;l<2;l++){ dp[i][j+1][max(0,k-1)][0]+=dp[i+1][j][k][l]; dp[i][j+1][max(0,k-1)][0]%=M; } //adding P for (int j=0;j<=2;j++) for (int k=0;k<2;k++) for (int l=0;l<2;l++){ dp[i][max(0,j-1)][k+1][1]+=dp[i+1][j][k][l]; dp[i][max(0,j-1)][k+1][1]%=M; } } int L_P=0,P_L=0; int ans=0; for (int i=0;i<N;i++){ //cout<<"I: "<<i<<endl; if (S[i]=='P'){ for (int j=0;j<=2;j++) for (int k=0;k<=2;k++) if (j+L_P<=2 && k+P_L<=2){ ans+=dp[i][j][k][0]; //cout<<"add "<<dp[i][j][k][0]<<endl; ans%=M; } } if (S[i]=='L'){ L_P++; P_L=max(0,P_L-1); } else{ P_L++; L_P=max(0,L_P-1); } } cout<<ans+1<<endl; return 0; }
#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...