Submission #998992

#TimeUsernameProblemLanguageResultExecution timeMemory
998992huutuanLinear Garden (IOI08_linear_garden)C++14
100 / 100
47 ms36524 KiB
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n, m; int f[N][3][3]; int dp(int i, int minpf, int maxpf){ if (minpf<-2 || maxpf>2) return 0; if (i==n+1) return 1; if (f[i][-minpf][maxpf]!=-1) return f[i][-minpf][maxpf]; int res=0; res=(res+dp(i+1, min({0, minpf-1, -1}), max({0, maxpf-1, -1})))%m; res=(res+dp(i+1, min({0, minpf+1, +1}), max({0, maxpf+1, +1})))%m; return f[i][-minpf][maxpf]=res; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i=0; i<=2; ++i) for (int j=0; j<=2; ++j) f[n+1][i][j]=1; for (int i=n; i>=1; --i){ for (int j=0; j<=2; ++j){ for (int k=0; k<=2; ++k){ int minpf=-j, maxpf=k; f[i][j][k]=0; if (j!=2) f[i][j][k]=(f[i][j][k]+f[i+1][-min({0, minpf-1, -1})][max({0, maxpf-1, -1})])%m; if (k!=2) f[i][j][k]=(f[i][j][k]+f[i+1][-min({0, minpf+1, +1})][max({0, maxpf+1, +1})])%m; } } } int ans=0, minpf=0, maxpf=0; for (int i=1; i<=n; ++i){ char c; cin >> c; if (c=='P'){ if (minpf!=-2) ans=(ans+f[i+1][-min({0, minpf-1, -1})][max({0, maxpf-1, -1})])%m; minpf=min({0, minpf+1, +1}), maxpf=max({0, maxpf+1, +1}); }else{ minpf=min({0, minpf-1, -1}), maxpf=max({0, maxpf-1, -1}); } } cout << (ans+1)%m << '\n'; 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...