Submission #503832

#TimeUsernameProblemLanguageResultExecution timeMemory
503832tabrLinear Garden (IOI08_linear_garden)C++17
95 / 100
1593 ms1384 KiB
#include <bits/stdc++.h> using namespace std; #ifdef tabr #include "library/debug.cpp" #else #define debug(...) #endif int main() { ios::sync_with_stdio(false); cin.tie(0); int n, mod; cin >> n >> mod; string s; cin >> s; vector<vector<vector<int>>> dp(7, vector<vector<int>>(7, vector<int>(7))); int mn = 3; int mx = 3; int now = 3; for (int i = 0; i < n; i++) { vector<vector<vector<int>>> new_dp(7, vector<vector<int>>(7, vector<int>(7))); for (int x = 1; x < 7; x++) { for (int y = x + 1; y < min(6, x + 3); y++) { for (int z = x; z <= y; z++) { if (y - min(z - 1, x) < 3) { new_dp[z - 1][min(z - 1, x)][y] += dp[z][x][y]; } if (min(z + 1, y) - x < 3) { new_dp[z + 1][x][max(z + 1, y)] += dp[z][x][y]; } } } } if (s[i] == 'P') { if (mx - min(mn, now - 1) < 3) { new_dp[now - 1][min(mn, now - 1)][mx]++; } now++; mx = max(mx, now); } else { now--; mn = min(mn, now); } swap(dp, new_dp); for (int x = 1; x < 7; x++) { for (int y = x + 1; y < min(6, x + 3); y++) { for (int z = x; z <= y; z++) { while (dp[z][x][y] >= mod) { dp[z][x][y] -= mod; } } } } } int ans = 1; for (int i = 0; i < 7; i++) { for (int j = i + 1; j < min(7, i + 3); j++) { for (int k = i; k <= j; k++) { ans += dp[k][i][j]; if (ans >= mod) { ans -= mod; } } } } cout << ans << '\n'; return 0; }
#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...