Submission #805101

#TimeUsernameProblemLanguageResultExecution timeMemory
805101BidoTeimaLinear Garden (IOI08_linear_garden)C++17
0 / 100
65 ms65536 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int N = 1e6 + 3; int mod; int n; int a[N]; int dp[2][2][2][N]; int rec(int idx, int p1, int p2, bool less){ if(idx == n){ return 1; } assert(a[idx]==0||a[idx]==1); if(p1!=-1&&p2!=-1&&dp[p1][p2][less][idx]!=-1){ return dp[p1][p2][less][idx]; } int ret = 0; if(p1==-1||p2==-1||p1!=p2){ for(int i = 0; less? i <= 1 : i <= a[idx]; i++){ assert(i!=2); ret += rec(idx+1,i,p1,less||(i<a[idx])); } } else if(p1 == 0){ if(a[idx]==1||less)ret+=rec(idx+1,1,p1,less); } else{ ret+=rec(idx+1,0,p1,less||a[idx]); } ret%=mod; if(p1!=-1&&p2!=-1){ dp[p1][p2][less][idx]=ret; } return ret; } int main() { memset(dp,-1,sizeof(dp)); cin>>n>>mod; for(int i = 0; i < n; i++){ char ch; cin>>ch; a[i]=ch=='P'; } cout<<(rec(0,-1,-1,0)-1+mod)%mod; 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...