제출 #228377

#제출 시각아이디문제언어결과실행 시간메모리
228377FieryPhoenixLinear Garden (IOI08_linear_garden)C++11
100 / 100
222 ms10404 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[2][3][3][2];//index, max(L-P), max(P-L), 0 for L int L_P[10000001],P_L[10000001]; int main() { //ios_base::sync_with_stdio(0);cin.tie(0); //freopen (".in","r",stdin); //freopen (".out","w",stdout); cin>>N>>M; cin>>S; for (int i=0;i<N;i++){ if (S[i]=='L'){ L_P[i+1]=L_P[i]+1; P_L[i+1]=max(0,P_L[i]-1); } else{ P_L[i+1]=P_L[i]+1; L_P[i+1]=max(0,L_P[i]-1); } } dp[0][0][0][0]=1; int ind=1,nind=0; int ans=0; 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[ind][j+1][max(0,k-1)][0]+=dp[nind][j][k][l]; dp[ind][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[ind][max(0,j-1)][k+1][1]+=dp[nind][j][k][l]; dp[ind][max(0,j-1)][k+1][1]%=M; } if (S[i]=='P'){ for (int j=0;j<=2;j++) for (int k=0;k<=2;k++) if (j+L_P[i]<=2 && k+P_L[i]<=2){ //cout<<"add "<<dp[ind][j][k][0]<<endl; ans+=dp[ind][j][k][0]; ans%=M; } } for (int j=0;j<=2;j++) for (int k=0;k<=2;k++) for (int l=0;l<2;l++){ dp[nind][j][k][l]=0; } swap(ind,nind); } cout<<(ans+1)%M<<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...