Submission #1248363

#TimeUsernameProblemLanguageResultExecution timeMemory
1248363LithaniumLinear Garden (IOI08_linear_garden)C++20
100 / 100
74 ms328 KiB
#include <bits/stdc++.h> using namespace std; bitset<1000005> num; int curr[3][3][2], pre[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 --) { memset(curr, 0, sizeof(curr)); for (int j = 0; j < 3; j ++) { for (int k = 0; k < 3; k ++) { for (int l = 0; l < 2; l ++) { if (i == N) { curr[j][k][l] = 1; continue; } int top = 1; if (l and num[i+1] == 0) top = 0; // put a 0 if (j < 2) curr[j][k][l] = pre[j+1][max(0, k-1)][l and (top == 0)]; // put a 1 if (top and k < 2) (curr[j][k][l] += pre[max(0, j-1)][k+1][l]) %= M; } } } memcpy(pre, curr, sizeof(pre)); } cout << pre[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...