# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
842973 | 2023-09-03T14:04:36 Z | anha3k25cvp | Linear Garden (IOI08_linear_garden) | C++14 | 169 ms | 65536 KB |
#include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define dl double #define st first #define nd second #define II pair <int, int> using namespace std; const int N = 5 + 1e5; const int inf = 7 + 1e9; int main() { #define TASKNAME "" ios_base :: sync_with_stdio (0); cin.tie (0); if ( fopen( TASKNAME".inp", "r" ) ) { freopen (TASKNAME".inp", "r", stdin); freopen (TASKNAME".out", "w", stdout); } int n, m; string s; cin >> n >> m >> s; n = s.size(); vector <int> a(n + 1, 0); for (int i = 1; i <= n; i ++) a[i] = s[i - 1] == 'P'; vector <vector <vector <int>>> f(n + 1, vector <vector <int>> (5, vector <int> (3, 0))); for (int mi = 0; mi <= 4; mi ++) for (int ma = mi; ma <= min(mi + 2, 4); ma ++) { vector <vector <vector <int>>> g(2, vector <vector <int>> (5, vector <int> (3, 0))); g[1][mi][ma - mi] = 1; for (int num = 0; num <= n; num ++) { for (int i = 0; i <= 4; i ++) for (int delta = 0; delta <= 2; delta ++) { g[0][i][delta] = g[1][i][delta]; g[1][i][delta] = 0; } for (int i = 0; i <= 4; i ++) for (int delta = 0; delta <= 2; delta ++) f[num][mi][ma - mi] = (f[num][mi][ma - mi] + g[0][i][delta]) % m; if (num == n) break; for (int i = 0; i <= 4; i ++) for (int delta = 0; delta <= 2; delta ++) { int j = i + delta; if (i > 0) { int i_ = min(i - 1, 1), j_ = max(j - 1, 1); g[1][i_][j_ - i_] = (g[1][i_][j_ - i_] + g[0][i][delta]) % m; } if (j < 4) { int i_ = min(i + 1, 3), j_ = max(j + 1, 3); g[1][i_][j_ - i_] = (g[1][i_][j_ - i_] + g[0][i][delta]) % m; } } } } int mi = 2, ma = 2, ans = 1; for (int i = 1; i <= n; i ++) { if (a[i] && mi > 0) { int mi_ = min(mi - 1, 1), ma_ = max(ma - 1, 1); ans = (ans + f[n - i][mi_][ma_ - mi_]) % m; } if (!a[i]) { mi = min(mi - 1, 1); ma = max(ma - 1, 1); } else { mi = min(mi + 1, 3); ma = max(ma + 1, 3); } } cout << ans; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 1372 KB | Output is correct |
2 | Correct | 10 ms | 1624 KB | Output is correct |
3 | Correct | 9 ms | 1624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 6488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 7260 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 135 ms | 19536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 169 ms | 23140 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 50 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 54 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 50 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 51 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 51 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |