Submission #1266341

#TimeUsernameProblemLanguageResultExecution timeMemory
1266341PlayVoltzLinear Garden (IOI08_linear_garden)C++20
100 / 100
63 ms36668 KiB
#include <bits/stdc++.h> using namespace std; const int mn = 1e6, smth = 3; int dp[mn][smth][smth]; signed main() { int n, mod; cin >> n >> mod; string s; cin >> s; dp[0][0][0] = 1; // l then p for (int i = 0; i < n; i++) { for (int j = 0; j < smth; j++) { for (int k = 0; k < smth; k++) { if (j != 2) { dp[i + 1][j + 1][max(0, k - 1)] += dp[i][j][k]; dp[i + 1][j + 1][max(0, k - 1)] %= mod; } if (k != 2) { dp[i + 1][max(0, j - 1)][k + 1] += dp[i][j][k]; dp[i + 1][max(0, j - 1)][k + 1] %= mod; } } } } int ls = 0, ps = 0; int prev = 0; for (int i = 0; i < n; i++) { // cout << i << " " << prev << " " << ls << " " << ps << "\n"; if (s[i] == 'P') { for (int j = 0; j + ls + 1 < smth; j++) for (int k = 0; k + max(0, ps - 1) < smth; k++) { prev += dp[n - i - 1][j][k]; prev %= mod; } ps++; ls--; ls = max(ls, 0); } else { ps--; ls++; ps = max(ps, 0); } } // for (int i = 0; i < smth; i++) // for (int j = 0; j < smth; j++) // cout << i << " " << j << " " << dp[3][i][j] << "\n"; cout << (prev + 1) % mod << "\n"; }
#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...