# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
64035 | 2018-08-03T08:33:42 Z | evpipis | Linear Garden (IOI08_linear_garden) | C++11 | 150 ms | 41964 KB |
#include <bits/stdc++.h> using namespace std; const int len = 1e6+1; int n, m, dp[len][3][3]; char str[len]; int add(int a, int b){ return (a+b)%m; } int main(){ scanf("%d %d %s", &n, &m, &str); for (int a = 0; a < 3; a++) for (int b = 0; b < 3; b++) dp[n][a][b] = 1; for (int i = n-1; i >= 0; i--) for (int a = -2; a <= 0; a++) for (int b = 0; b <= 2; b++){ int ans = 0; if (a != -2) ans = add(ans, dp[i+1][a-1+2][max(b-1, 0)]); if (b != +2) ans = add(ans, dp[i+1][min(a+1, 0)+2][b+1]); dp[i][a+2][b] = ans; } int mn = 0, mx = 0, ans = 1; for (int i = 0; i < n; i++){ if (str[i] == 'P' && mn != -2) ans = add(ans, dp[i+1][mn-1+2][max(mx-1, 0)]); if (str[i] == 'L') mn = mn-1, mx = max(mx-1, 0); else mn = min(mn+1, 0), mx = mx+1; } 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 | 3 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 496 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 636 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 752 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 756 KB | Output is correct |
2 | Correct | 3 ms | 756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 764 KB | Output is correct |
2 | Correct | 2 ms | 768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 772 KB | Output is correct |
2 | Correct | 3 ms | 904 KB | Output is correct |
3 | Correct | 3 ms | 912 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 1556 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 1592 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 3040 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 3628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 12548 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 62 ms | 16164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 76 ms | 20720 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 100 ms | 25404 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 149 ms | 39916 KB | Output is correct |
2 | Correct | 150 ms | 40860 KB | Output is correct |
3 | Correct | 145 ms | 41964 KB | Output is correct |