Submission #799667

#TimeUsernameProblemLanguageResultExecution timeMemory
799667mosiashvililukaLinear Garden (IOI08_linear_garden)C++14
100 / 100
95 ms65008 KiB
#include<bits/stdc++.h> using namespace std; int a,b,c,d,e,i,j,ii,jj,zx,xc,mod,dp[1000009][4][4],bo1,bo2,x,xx,BO1,BO2,pas,mn,mx,jm; string s; int main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>a>>mod; cin>>s;s="0"+s; dp[0][0][0]=1; for(i=0; i<a; i++){ for(bo1=0; bo1<=2; bo1++){ for(bo2=0; bo2<=2; bo2++){ if(bo1+bo2>2) continue; //-1 BO1=bo1+1; BO2=max(bo2-1,0); if(BO1<=2){ dp[i+1][BO1][BO2]+=dp[i][bo1][bo2];dp[i+1][BO1][BO2]%=mod; } //1 BO2=bo2+1; BO1=max(bo1-1,0); if(BO2<=2){ dp[i+1][BO1][BO2]+=dp[i][bo1][bo2];dp[i+1][BO1][BO2]%=mod; } } } } mn=mx=0;jm=0; for(i=1; i<=a; i++){ if(s[i]=='L'){ jm--; if(jm<0) mn=max(mn,0-jm); if(jm>0) mx=max(mx,jm); continue; } int MN=mn,MX=mx; jm--; if(jm<0) mn=max(mn,0-jm); if(jm>0) mx=max(mx,jm); // for(bo1=0; bo1<=2; bo1++){ for(bo2=0; bo2<=2; bo2++){ BO1=max(mn,bo1-jm); BO2=max(mx,jm+bo2); if(BO1+BO2>2) continue; pas+=dp[a-i][bo1][bo2];pas%=mod; } } // mn=MN;mx=MX; jm+=2; if(jm<0) mn=max(mn,0-jm); if(jm>0) mx=max(mx,jm); } pas++;pas%=mod; cout<<pas; 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...