Submission #1248317

#TimeUsernameProblemLanguageResultExecution timeMemory
1248317LithaniumLinear Garden (IOI08_linear_garden)C++20
95 / 100
165 ms78808 KiB
#include <bits/stdc++.h> using namespace std; bitset<1000005> num; int dp[1000005][2][2]; int N, M; int solve(int n, short L, short P, bool lim) { if (L > 2 or P > 2) return 0; if (n == N) return 1; if (!lim and max(L, P) < 2 and dp[n][L][P] != -1) return dp[n][L][P]; int top = 1; if (lim and num[n+1] == 0) top = 0; int ans = 0; // put a 0 if (L != 2) (ans += solve(n+1, L+1, max(0, P-1), lim and (top == 0))) %= M; // put a 1 if (top and P != 2) (ans += solve(n+1, max(0, L-1), P+1, lim)) %= M; if (!lim and max(L, P) < 2) return dp[n][L][P] = ans; return ans; } int main() { memset(dp, -1, sizeof(dp)); cin >> N >> M; for (int i = 1; i <= N; i ++) { char c; cin >> c; if (c == 'P') num[i] = 1; } cout << solve(0, 0, 0, 1); }
#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...