제출 #1248316

#제출 시각아이디문제언어결과실행 시간메모리
1248316LithaniumLinear Garden (IOI08_linear_garden)C++20
80 / 100
188 ms114032 KiB
#include <bits/stdc++.h> using namespace std; bitset<1000005> num; int dp[1000005][3][3]; int N, M; int solve(int n, short L, short P, bool lim) { if (L == 2 and P == 2) return 0; if (L > 2 or P > 2) return 0; if (n == N) return 1; if (!lim and dp[n][L][P] != -1) return dp[n][L][P]; int top = 1; if (lim and num[n+1] == 0) top = 0; // put a 0 int ans = solve(n+1, L+1, max(0, P-1), lim and (top == 0)); // put a 1 if (top) (ans += solve(n+1, max(0, L-1), P+1, lim)) %= M; if (!lim) 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...