Submission #1248319

#TimeUsernameProblemLanguageResultExecution timeMemory
1248319LithaniumLinear Garden (IOI08_linear_garden)C++20
95 / 100
172 ms74892 KiB
#include <bits/stdc++.h> using namespace std; bitset<1000005> num; int dp01[1000005]; int dp10[1000005]; int dp11[1000005]; int N, M; int read(int n, char L, char P) { if (L == 0 and P == 1) return dp01[n]; if (L == 1 and P == 1) return dp11[n]; if (L == 1 and P == 0) return dp10[n]; } void write(int n, char L, char P, int x) { if (L == 0 and P == 1) dp01[n] = x; if (L == 1 and P == 1) dp11[n] = x; if (L == 1 and P == 0) dp10[n] = x; } int solve(int n, char L, char P, bool lim) { if (L > 2 or P > 2) return 0; if (n == N) return 1; if (!lim and max(L, P) == 1 and read(n, L, P) != -1) return read(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) == 1) write(n, L, P, ans); return ans; } int main() { memset(dp01, -1, sizeof(dp01)); memset(dp10, -1, sizeof(dp10)); memset(dp11, -1, sizeof(dp11)); 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); }

Compilation message (stderr)

linear_garden.cpp: In function 'int read(int, char, char)':
linear_garden.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
   14 | }
      | ^
#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...