| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 503831 | tabr | Linear Garden (IOI08_linear_garden) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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<mint>>(7, vector<mint>(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<mint>>(7, vector<mint>(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;
}