# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
197809 | 2020-01-23T10:50:06 Z | SamAnd | Linear Garden (IOI08_linear_garden) | C++17 | 468 ms | 2424 KB |
#include <bits/stdc++.h> using namespace std; const int N = 1000006, m = 5; int M; int n; char a[N]; int dp[m][m][m]; int ndp[m][m][m]; int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); #endif // SOMETHING scanf("%d%d", &n, &M); scanf(" %s", a); int minu = 2, maxu = 2, p = 2; for (int i = 0; i < n; ++i) { memset(ndp, 0, sizeof ndp); for (int minu = 0; minu < m; ++minu) { for (int maxu = minu; maxu < m; ++maxu) { for (int p = minu; p <= maxu; ++p) { int yp = p + 1; if (abs(yp - minu) > 2 || abs(yp - maxu) > 2) continue; int yminu = min(yp, minu); int ymaxu = max(yp, maxu); ndp[yminu][ymaxu][yp] = (ndp[yminu][ymaxu][yp] + dp[minu][maxu][p]) % M; } for (int p = minu; p <= maxu; ++p) { int yp = p - 1; if (abs(yp - minu) > 2 || abs(yp - maxu) > 2) continue; int yminu = min(yp, minu); int ymaxu = max(yp, maxu); ndp[yminu][ymaxu][yp] = (ndp[yminu][ymaxu][yp] + dp[minu][maxu][p]) % M; } } } if (a[i] == 'P') { int yp = p - 1; if (!(abs(yp - minu) > 2 || abs(yp - maxu) > 2)) { int yminu = min(yp, minu); int ymaxu = max(yp, maxu); ndp[yminu][ymaxu][yp] = (ndp[yminu][ymaxu][yp] + 1) % M; } } if (a[i] == 'P') ++p; else --p; minu = min(minu, p); maxu = max(maxu, p); memcpy(dp, ndp, sizeof ndp); } int ans = 0; for (int minu = 0; minu < m; ++minu) { for (int maxu = minu; maxu < m; ++maxu) { for (int p = minu; p <= maxu; ++p) { ans = (ans + dp[minu][maxu][p]) % M; } } } ans = (ans + 1) % M; printf("%d\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 476 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
# | 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 | 504 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 376 KB | Output is correct |
3 | Correct | 4 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 144 ms | 968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 191 ms | 1152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 244 ms | 1364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 294 ms | 1580 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 464 ms | 2396 KB | Output is correct |
2 | Correct | 458 ms | 2316 KB | Output is correct |
3 | Correct | 468 ms | 2424 KB | Output is correct |