Submission #466839

#TimeUsernameProblemLanguageResultExecution timeMemory
466839dutchLinear Garden (IOI08_linear_garden)C++17
100 / 100
223 ms2408 KiB
#include <bits/stdc++.h> using namespace std; int N, M, dp[2][3][3], result; string S; #define s(i) (S[i] == 'P') signed main(){ cin.tie(0)->sync_with_stdio(0); cin >> N >> M >> S; dp[0][0][0] = 1; for(int i=N; --i>=0; ){ int prev[2][3][3] = {}; swap(prev, dp); for(bool a : {0, 1}){ for(int x : {0, 1, 2}){ for(int y : {0, 1, 2}){ if(x < 2) (dp[!s(i) && a][x + 1][max(y - 1, 0)] += prev[a][x][y]) %= M; if(y < 2) (dp[!s(i) || a][max(x - 1, 0)][y + 1] += prev[a][x][y]) %= M; } } } } for(int x : {0, 1, 2}) for(int y : {0, 1, 2}) (result += dp[0][x][y]) %= M; cout << result; }
#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...