Submission #1248358

#TimeUsernameProblemLanguageResultExecution timeMemory
1248358LithaniumLinear Garden (IOI08_linear_garden)C++20
95 / 100
103 ms70868 KiB
#include <bits/stdc++.h> using namespace std; bitset<1000005> num; int dp[1000005][3][3][2]; int N, M; int main() { cin >> N >> M; for (int i = 1; i <= N; i ++) { char c; cin >> c; if (c == 'P') num[i] = 1; } for (int i = N; i >= 0; i --) { for (int j = 0; j < 3; j ++) { for (int k = 0; k < 3; k ++) { for (int l = 0; l < 2; l ++) { if (i == N) { dp[i][j][k][l] = 1; continue; } int top = 1; if (l and num[i+1] == 0) top = 0; // put a 0 if (j < 2) dp[i][j][k][l] = dp[i+1][j+1][max(0, k-1)][l and (top == 0)]; // put a 1 if (top and k < 2) (dp[i][j][k][l] += dp[i+1][max(0, j-1)][k+1][l]) %= M; } } } } cout << dp[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...