Submission #1266672

#TimeUsernameProblemLanguageResultExecution timeMemory
1266672SnowRaven52Linear Garden (IOI08_linear_garden)C++20
100 / 100
29 ms24804 KiB
#include <bits/stdc++.h> using namespace std; int main() { // freopen("main.in", "r", stdin); // freopen(".out", "w", stdout); ios::sync_with_stdio(false); cin.tie(nullptr); int N; int M; cin >> N >> M; string S; cin >> S; auto nxt = [&](int st, char ch)->int { switch (st) { case 0: return (ch=='L'? 2 : 1); case 1: return (ch=='L'? 2 : 3); case 2: return (ch=='L'? 5 : 1); case 3: return (ch=='L'? 4 : -1); case 4: return (ch=='L'? 5 : 3); case 5: return (ch=='L'? -1 : 4); } return -1; }; vector<array<int,6>> dp(N+1); for (int s = 0; s < 6; s++) dp[0][s] = 1 % M; for (int len = 1; len <= N; len++) { for (int s = 0; s < 6; s++) { long long v = 0; int a = nxt(s, 'L'); if (a != -1) v += dp[len-1][a]; int b = nxt(s, 'P'); if (b != -1) v += dp[len-1][b]; dp[len][s] = int(v % M); } } long long ans = 1 % M; int st = 0; for (int i = 0; i < N; i++) { int rem = N - i; if (S[i] == 'P') { int a = nxt(st, 'L'); if (a != -1) ans = (ans + dp[rem-1][a]) % M; st = nxt(st, 'P'); } else { st = nxt(st, 'L'); } } cout << (ans % M) << endl; }
#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...