# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
54132 | 2018-07-02T12:35:51 Z | 0^0(#1448) | Linear Garden (IOI08_linear_garden) | C++11 | 202 ms | 99440 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) { int ret = 1; while (idx < n) { if (str[idx] == 'L') { mins = min(-1, mins - 1); maxs = max(-1, maxs - 1); } else { ret = (ret+dp[idx + 1][min(-1, mins - 1) + 2][max(-1, maxs - 1) + 2]) % mod; mins = (min(1, mins + 1)); maxs = (max(1, maxs + 1)); } idx++; } return ret; } 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 | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 668 KB | Output is correct |
2 | Correct | 2 ms | 668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 668 KB | Output is correct |
2 | Correct | 2 ms | 668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 852 KB | Output is correct |
2 | Correct | 3 ms | 980 KB | Output is correct |
3 | Correct | 3 ms | 980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2772 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 6612 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 7764 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 31248 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 83 ms | 40192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 100 ms | 51104 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 125 ms | 62188 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Memory limit exceeded | 202 ms | 99440 KB | |
2 | Halted | 0 ms | 0 KB | - |