# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
54131 | 2018-07-02T12:33:03 Z | 0^0(#1448) | Linear Garden (IOI08_linear_garden) | C++11 | 222 ms | 115292 KB |
#include <bits/stdc++.h> using namespace std; int n, mod; char str[1000005]; int dp[1000005][5][5]; int get_ans(int idx, int mins, int maxs) { if (mins < -2 || maxs > 2)assert(false); if (idx == n)return 1; if (str[idx] == 'L')return get_ans(idx + 1, min(-1, mins - 1), max(-1, maxs - 1)); return (get_ans(idx + 1, min(1, mins + 1), max(1, maxs + 1)) + dp[idx + 1][min(-1, mins - 1) + 2][max(-1, maxs - 1) + 2]) % mod; } int main() { scanf("%d%d%s", &n, &mod, str); for (int i = -2; i <= 2; i++) for (int j = i; j <= 2; j++) dp[n][i+2][j+2] = 1; for (int i = n - 1; i >= 1; i--) for (int j = -2; j <= 2; j++) for (int k = j; k <= 2; k++) { dp[i][j+2][k+2] = 0; if (j - 1 >= -2)dp[i][j+2][k+2] += dp[i + 1][min(-1, j - 1) + 2][max(-1, k - 1) + 2]; if (k + 1 <= 2)dp[i][j+2][k+2] += dp[i + 1][min(1, j + 1) + 2][max(1, k + 1) + 2]; dp[i][j+2][k+2] %= mod; } int ans = 0; if (str[0] == 'L')ans = get_ans(1, -1, -1); else ans = (get_ans(1, 1, 1) + dp[1][1][1]) % mod; printf("%d\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 356 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 700 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 700 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 700 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 700 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 700 KB | Output is correct |
2 | Correct | 3 ms | 716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 716 KB | Output is correct |
2 | Correct | 3 ms | 716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 884 KB | Output is correct |
2 | Correct | 4 ms | 1012 KB | Output is correct |
3 | Correct | 4 ms | 1020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2904 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 3200 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 7552 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 8960 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 68 ms | 36096 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 105 ms | 46636 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 59140 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Memory limit exceeded | 132 ms | 72064 KB |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Memory limit exceeded | 222 ms | 115292 KB | |
2 | Halted | 0 ms | 0 KB | - |